[BOJ] 1918번 데이터체커 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        List<Point> points = new ArrayList<>();
        Stack<Point> stack = new Stack<>();

        while (N-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            // 왼쪽 끝점, 오른쪽 끝점을 구분한다.
            // x 좌표, 중심 좌표, 왼쪽 여부에 대한 정보를 담는 객체 리스트를 생성한다.
            points.add(new Point(x - r, x, true));
            points.add(new Point(x + r, x, false));
        }

        // 점의 x 좌표를 기준으로 정렬한다.
        points.sort(Comparator.comparingInt(o -> o.x));

        for (Point point : points) {
            // 원의 왼쪽 점이면 스택에 넣는다.
            if (point.isLeft) {
                stack.push(point);
                continue;
            }

            // 오른쪽 점인 경우 스택의 탑과 중심이 같다면 같은 원에 대한 좌표이므로 스택에서 뺀다.
            if (stack.peek().c == point.c) {
                stack.pop();
            } else {
                // 그렇지 않으면 둘이 다른원이다 => 겹치는 원이 존재한다.
                System.out.println("NO");
                return;
            }
        }

        // 리스트 순회가 끝났다면 겹치는 부분은 없었던 것이다.
        System.out.println("YES");
    }

    static class Point {

        int x;
        int c;
        boolean isLeft;

        public Point(int x, int c, boolean isLeft) {
            this.x = x;
            this.c = c;
            this.isLeft = isLeft;
        }
    }
}

📄 해설

접근

• 접근을 제대로 하지 못했다. 문제에서 힌트로 제공된 수식을 사용하는 풀이를 적용했을 때, 98% 에서 틀렸는데, 다른 사람의 풀이를 찾아봤더니 전혀 다른 풀이여서 아직 그 이유를 밝히지 못했다..
• 우선 위 풀이에서의 접근은, 각 원마다 왼쪽 끝점과 오른쪽 끝점을 구분해서 x 좌표, 중심 좌표, 왼쪽 여부에 대한 정보를 담는 Point 클래스 객체를 새로 생성하고, 리스트를 만든다.
• 해당 리스트를 x 좌표를 기준으로 정렬하고, 리스트를 순회하면서 왼쪽 끝점인지 오른쪽 끝점인지에 따라 처리를 하고, 겹치는 원이 있는지 없는지를 확인한다.

과정

• Point 객체를 담을 리스트와 스택을 선언하고, N 개의 원의 정보를 입력 받는다.
• 입력 받은 정보에 따라 왼쪽 끝점과 오른쪽 끝점에 대한 객체들을 새롭게 생성하여 리스트에 추가한다.
• 입력이 끝나면 점의 x 좌표를 기준으로 해당 리스트를 정렬하고, 리스트를 순회화면서 아래 동작을 반복한다.
  • 왼쪽 끝점일 경우, 스택에 추가한다.
  • 오른쪽 끝점일 경우 스택의 탑과 중심 좌표가 같다면, 각 점은 같은 원을 구성하므로, 스택에서 뺀다.
  • 스택의 탑과 중심 좌표가 같지 않다면, 둘은 다른 원이므로, 겹치는 원이 존재한다는 뜻이므로 NO 를 출력한다.
• 리스트 순회가 정상적으로 종료되었다면, 겹치는 원은 없었던 것이므로 YES 를 출력한다.