[백준] 22942번 - 데이터 체커 (java)

Baekjoon 22942 - 데이터 체커 (클릭 시 이동)

문제

원 이동하기 2 문제를 만들고 만든 데이터가 문제의 조건에 맞는지 확인하는 코드를 작성해야한다.

해당 문제의 데이터는 아래 조건들을 만족해야한다.

1. 모든 원의 중심 좌표는 x축 위에 존재해야 한다.
2.  N개의 원 중 임의의 두 원을 선택했을 때, 교점이 존재하지 않아야 한다. 즉, 하나의 원이 다른 원 안에 존재하거나 외부에 존재한다.

데이터 형식은 원의 개수 N이랑 각 원의 중심 x좌표, 원의 반지름 r만 주어진다. 따라서, 2번 조건을 만족하는지만 확인하면 된다.

주어진 데이터가 해당 조건을 만족하는지 확인해보자.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (하단 참고)	1024 MB	390	103	67	32.843%

입력

첫 번째 줄에는 원의 개수 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 원의 중심 x좌표, 원의 반지름 r이 공백으로 구분되어 주어진다.

출력

데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다.

풀이

괄호 쌍 찾기 문제를 생각하면 조금더 이해하기 쉽다.

1. 각 원에 번호를 매기고 원의 왼쪽 점과 오른쪽 점의 위치를 구한다.
2. [번호, 점] 으로 Collection에 저장한 후 점의 위치를 오름차순으로 정렬한다.
3. 정렬할 때 똑같은 위치에 두개의 점이 있다면 NO를 출력한다.
4. Stack을 이용하여 번호의 쌍이 맞게 나오는지 확인한다.

최종 소스코드

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

public class BJ_G5_22942_데이터_체커 {

    static int N;
    static boolean flag = false;
    static StringTokenizer st;

    static class Checker implements Comparable<Checker>{
        int no;
        int dot;

        public Checker(int no, int dot) {
            super();
            this.no = no;
            this.dot = dot;
        }

        @Override
        public int compareTo(Checker o) {
            if(this.dot == o.dot) flag = true;    // 같은 위치에 점이 존재한다
            return this.dot - o.dot;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Checker> pq = new PriorityQueue<>();
        Stack<Integer> stack = new Stack<>();

        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            pq.add(new Checker(i,x-r));
            pq.add(new Checker(i,x+r));
        }

        if(flag) {
            System.out.println("NO");
            return;
        }

        while(!pq.isEmpty()) {
            if(stack.isEmpty()) {
                stack.push(pq.poll().no);
            }
            else {
                int number = pq.poll().no;
                if(stack.peek() == number) {    // 번호와 스택의 Top이 같다면 스택에서 뺀다
                    stack.pop();
                }
                else{
                    stack.push(number);        // 다르다면 스택에 넣는다.
                }
            }
        }

        if(stack.isEmpty()) {            // 스택이 비어있다 == 모두 쌍이 맞다.
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }

    }
}