[Softeer]사물인식 최소 면적 산출 프로그램

소프티어 레벨 1, 2 는 바로바로 다 풀고 레벨 3 풀수 있는 문제 부터 푸는 중이다.

 

어제 푼 문제는

[HSAT 2회 정기 코딩 인증평가 기출] 사물인식 최소 면적 산출 프로그램

https://softeer.ai/practice/6277

위 문제이다.

 

각각의 점이 있고, 점마다 색깔이 있는데

점의 좌표와 색깔이 주어지면, 직사각형 안에 각 점들의 색깔이 최소 1개 이상은 포함하고 있는 

최소 직사각형의 너비를 구하는 문제이다.

 

첫 시도.

각 점들을 꼭지점으로 하여 직사각형 넓이를 구하고, 넓이에 들어가는 점들의 색깔을 카운트 했다.

틀렸다..

Subtask 1,2,3,4 중 Subtask 1 만 맞았다.

이유를 몰라서 연습문제 톡을 봐보니까,

각 점들을 꼭지점으로 하여 직사각형으로 구했을때 틀린 것이라고 누가 글을 올린 걸 보았다.

내가 틀린 이유를 이렇게 바로 확인할 수 있다는건 엄청난 운이라 생각한다...(올려주신분 감사합니다ㅠㅠ)

 

두번쨰 시도,

각 점들의 x좌표, y좌표를 set 으로 담아서, 가능한 경우의 모든 직사각형 안에 각 점들의 색깔을 카운트 했다.

이때는 0,0 좌표에서 각 좌표 [x][y] 까지 누적 sum 을 구하고

필요한 직사각형은 [x2][y2] - [x1-1][y2]-[x2][y1-1] +[x1-1][y1-1] 과 같이 구해놓은 sum 에서 필요한 면적을 계산하는 방법을 사용.

이번에는 메모리 초과로 틀렸다...

 

세번째 시도,

각 sum[x][y]를 좌표 크기 1 마다 구했엇는데 이게 문제같다.

모든 좌표의 누적 합을 구할필요 없이, 구해야 하는 직사각형 넓이의 x,y 좌표마다 구하면 되지 않을까?

 

결과는 성공이다ㅠㅠ 만세.

이번에는 틀린 이유를 바로 알수 있는 운이 좀 있었다.

 

import java.io.*;
import java.util.*;

public class Main {

    static class Pair{
        int x,y;
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }


    static class ColorSet{
        int[] colorK;
        ColorSet(int k){
            this.colorK = new int[k];
        }

        void addColor(int k){
            colorK[k] += 1;
        }

        void addColorSet(ColorSet colorSet){
            if(colorSet == null) return;
            for(int i=0; i<colorSet.colorK.length; i++){
                colorK[i] += colorSet.colorK[i];
            }
        }

        void subjectColorSet(ColorSet colorSet){
            if(colorSet == null) return;
            for(int i=0; i<colorSet.colorK.length; i++){
                colorK[i] -= colorSet.colorK[i];
            }
        }


        int getBlockColorCnt(ColorSet colorSetX, ColorSet colorSetY, ColorSet colorSetXY){
            int ans = 0;
            int[] blockC = new int[colorK.length];
            for(int i=0; i<blockC.length; i++){
                blockC[i] = this.colorK[i] - colorSetX.colorK[i] - colorSetY.colorK[i] + colorSetXY.colorK[i];
                if(blockC[i] > 0){
                    ans++;
                }
            }
            return ans;
        }

    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        List<Pair>[] list = new ArrayList[k];
        for(int i=0; i<k; i++){
            list[i] = new ArrayList<>();
        }

        int minX = 1000;
        int maxX = -1000;
        int minY = 1000;
        int maxY = -1000;

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int color = Integer.parseInt(st.nextToken())-1;
            list[color].add(new Pair(x,y));
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            minY = Math.min(minY, y);
            maxY = Math.max(maxY, y);
        }

        int width = maxX - minX + 1;
        int height = maxY - minY + 1;

        ColorSet[][] colorSets = new ColorSet[height+1][width+1];
        Set<Integer> setX = new TreeSet<>();
        Set<Integer> setY = new TreeSet<>();
        setX.add(0);
        setY.add(0);
        for(int i=0; i<k; i++){
            List<Pair> pairs = list[i];
            for(Pair pair : pairs){
                int adX = pair.x - minX +1;
                int adY = pair.y - minY +1;
                if(colorSets[adY][adX] == null){
                    colorSets[adY][adX] = new ColorSet(k);
                }
                colorSets[adY][adX].addColor(i);
                setX.add(adX);
                setY.add(adY);
            }
        }

        List<Integer> listX = new ArrayList<>(setX);
        List<Integer> listY = new ArrayList<>(setY);

        ColorSet[][] colorSum = new ColorSet[setY.size()][setX.size()];
        for(int i=0; i<listY.size(); i++){
            for(int j=0; j<listX.size(); j++){
                colorSum[i][j] = new ColorSet(k);
                if(i==0 || j==0){
                    continue;
                }
                colorSum[i][j].addColorSet(colorSets[listY.get(i)][listX.get(j)]);
                colorSum[i][j].addColorSet(colorSum[i-1][j]);
                colorSum[i][j].addColorSet(colorSum[i][j-1]);
                colorSum[i][j].subjectColorSet(colorSum[i-1][j-1]);
            }
        }

        int ans = 4000000;
        for(int i1=1; i1<listY.size(); i1++){
            for(int j1=1; j1<listX.size(); j1++){
                for(int i2=1; i2<listY.size(); i2++){
                    if(i1 > i2) continue;;
                    for(int j2=1; j2<listX.size(); j2++){
                        if(j1 > j2) continue;

                        int cnt = colorSum[i2][j2].getBlockColorCnt(colorSum[i1-1][j2], colorSum[i2][j1-1], colorSum[i1-1][j1-1]);
                        if(cnt == k){
                            int tempSum = (listY.get(i2) - listY.get(i1)) * (listX.get(j2) - listX.get(j1));
                            ans = Math.min(tempSum, ans);
                        }
                    }
                }
            }
        }

        bw.write(String.valueOf(ans));
        bw.close();
    }

}