[Gold II] 직각다각형 - 17611

문제 링크

분류

누적 합, 정렬, 스위핑

문제 설명

다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형을 단순다각형이라고 부른다. 다각형의 각 변이 x축과 y축에 평행한 다각형을 직각다각형이라 부른다. 단순다각형이면서 직각다각형을 단순직각다각형이라 부른다. 아래 두 그림은 단순직각다각형의 예를 보여준다.

단순직각다각형이 주어질 때, 수평선 H가 다각형의 수직선분과 몇 번 교차하는지 또는 수직선 V가 다각형의 수평선분과 몇 번 교차하는지 알고자 한다. 첫 번째 그림에서 수평선 H는 4개의 수직선분과 교차하고 수직선 V는 2개의 수평선분과 교차한다. 두 번째 그림은 첫 번째 그림에서 수평선 H의 위치를 조금 위로 옮긴 것으로 8개의 수직선분과 교차하게 된다.

이때, 단순직각다각형과 가장 많이 교차하는 수평선 H와 수직선 V의 위치를 찾아 그때의 교차 횟수를 구하고자 한다. 단, 수평선 H는 다각형의 어떤 수평선분과도 겹처 놓여서는 안 되고, 유사하게 수직선 V는 다각형의 어떤 수직선분과도 겹쳐 놓여서는 안 된다.

수평선 H의 위치를 잘 정해서 주어진 단순직각다각형의 수직선분과 가장 많이 교차하는 지점을 찾을 때, 그 때의 교차 횟수를 h라 하고, 유사하게 수직선 V와 주어진 단순직각다각형의 수평선분과 가장 많이 교차하는 횟수를 v라 할 때, max(h, v)를 출력하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (x_i, y_i)가 차례대로 주어진다. 주어지는 꼭지점들의 순서는 시계방향이다. 다각형의 꼭지점을 나타내는 각 좌표값은 정수이며, -500,000 ≤ x_i, y_i ≤ 500,000이다.

출력

max(h, v)를 출력한다.

 

실패한 풀이(구현 방식으로 풀이)

시간 복잡도 O(n^2) 공간 복잡도 O(n)

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

public class Main {
    public static class Pos{
        int start;
        int end;
        public Pos(int x,int y){
            this.start = x;
            this.end = y;
        }
    }
    public static int sti(StringTokenizer st) {
        return Integer.parseInt(st.nextToken());
    }

    public static long stl(StringTokenizer st) {
        return Long.parseLong(st.nextToken());
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        // 입력 받기
        int ans = 0;
        int n = Integer.parseInt(br.readLine()); // 첫 번째 줄의 숫자를 읽어서 n에 저장합니다.
        int[][] pairs = new int[n][2]; // n개의 쌍을 저장하기 위한 2차원 배열을 생성합니다.
        List<Pos> heights = new ArrayList<Pos>();
        TreeSet<Integer> memoryHeight = new TreeSet<Integer>();
        List<Pos> weights = new ArrayList<Pos>();
        TreeSet<Integer> memoryWeight = new TreeSet<Integer>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine()); // 각 줄을 읽어서 StringTokenizer로 분리합니다.
            pairs[i][0] = Integer.parseInt(st.nextToken()); // 첫 번째 정수를 배열에 저장합니다.
            pairs[i][1] = Integer.parseInt(st.nextToken()); // 두 번째 정수를 배열에 저장합니다.
            memoryHeight.add(pairs[i][1]);
            memoryWeight.add(pairs[i][0]);
        }
        for(int i=1; i<n;i++){
           if(pairs[i-1][0]==pairs[i][0])
               heights.add(new Pos(pairs[i-1][1],pairs[i][1]));
           if(pairs[i-1][1]==pairs[i][1])
               weights.add(new Pos(pairs[i-1][0],pairs[i][0]));
        }
        weights.add(new Pos(pairs[0][0],pairs[n-1][0]));

        int start = memoryHeight.first();
        int end = memoryHeight.last();
        int count = 0;
        for (int i = start; i <= end; i++) {
            int tmp=0;
            for (Pos height : heights) {
                int max = Math.max(height.start,height.end);
                int min = Math.min(height.start,height.end);
                if(min<=i&&i<max)
                    tmp++;
            }
            count = Math.max(count,tmp);
        }
        int h = count;

        start = memoryWeight.first();
        end = memoryWeight.last();
        count = 0;
        for (int i = start; i <= end; i++) {
            int tmp=0;
            for (Pos weight :weights ) {
                int max = Math.max(weight.start,weight.end);
                int min = Math.min(weight.start,weight.end);
                if(min<=i&&i<max)
                    tmp++;
            }
            count = Math.max(count,tmp);
        }
        int w = count;
        System.out.println(h);
        System.out.println(w);

        System.out.println(Math.max(h,w));
        br.close();
        bw.flush();
        bw.close();

    }
}

1. 각 꼭지점을 입력 받으면서, 각각의 x 좌표와 y 좌표를 TreeSet에 저장합니다.
2. 수평선분과 수직선분을 분류하여 각각의 리스트에 추가합니다.
3. 가능한 모든 y 좌표를 순회하면서, 해당 위치에서 수평선이 교차하는 수직선분의 개수를 구합니다.
4. 가능한 모든 x 좌표를 순회하면서, 해당 위치에서 수직선이 교차하는 수평선분의 개수를 구합니다.
5. 교차하는 수직선분의 개수와 교차하는 수펑선분의 개수 중 큰 값을 출력 합니다.

성공한 풀이(스위핑)

시간 복잡도 O(n) 공간 복잡도 O(n)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main2 {
    private static final int CAIL = 500000;
    private static final int MAX = 1000010;
    private static int[] CountX = new int[MAX];
    private static int[] CountY = new int[MAX];
    private static List<Pos> vertex = new ArrayList<>();
    public static class Pos{
        int start;
        int end;
        public Pos(int x,int y){
            this.start = x;
            this.end = y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // -500000~ 이므로 모든 좌표가 양수가 되도록 500000을 더한다.
            a +=CAIL;
            b +=CAIL;
            // 꼭지점의 대한 모든 정보를 저장한다.
            vertex.add(new Pos(a,b));
        }
        // 꼭짓점 x 좌표값이 다음 번째 x 좌표값과 같다면 y축 선분이 만들어짐
        // 꼭짓점 y 좌표값이 다음 번째 y 좌표값과 같다면 x축 선분이 만들어짐
        for (int i = 0; i < N; i++) {
            int x = vertex.get(i).start;
            int y = vertex.get(i).end;
            int nx = vertex.get((i+1)%N).start;
            int ny = vertex.get((i+1)%N).end;
            // y축 선분 생성, 누적합 기록 첫 선분 시작점 에서 +1, 끝에서 -1
            if(x == nx){
                int StartY = Math.min(y,ny);
                int EndY = Math.max(y,ny);
                CountY[StartY]++;
                CountY[EndY]--;
            } else{
                int StartX = Math.min(x,nx);
                int EndX = Math.max(x,nx);
                CountX[StartX]++;
                CountX[EndX]--;
            }
        }
        // 누적합 계산 작업
        for (int i = 1; i < MAX; i++) {
            CountX[i]+=CountX[i-1];
            CountY[i]+=CountY[i-1];
        }
        int answer = 0;
        // 계산된 누적값의 합계 중 가장 큰 값을 찾기
        for (int i = 1; i < MAX; i++) {
            answer = Math.max(Math.max(CountX[i],CountY[i]),answer);
        }
        System.out.println(answer);
    }
}

1. 각 꼭지점을 입력 받으면서, 좌표값에 일정 값을 더해 모든 좌표가 양수가 되도록 합니다.
2. 각 선분에 대해, 해당 선분이 시작하는 위치에서 카운터를 1 증가시키고, 선분이 끝나는 위치에서 카운터를 1 감소시킵니다. 이를 통해 각 선분이 수평인지 수직인지에 따라 Count_X 배열과 Count_Y 배열에 이벤트를 기록합니다.
3. 각 배열을 순회하면서, 이전 위치에서의 카운터 값을 현재 위치에 더해줍니다. 이를 통해 각 위치에서의 누적 교차 이벤트 개수를 구합니다.
4. 각 위치에서의 누적 교차 이벤트 개수 중 최대값을 찾아 출력합니다.