[BOJ - JAVA] 22942 - 데이터 체커(스택)

# 주소

https://www.acmicpc.net/problem/22942

22942번: 데이터 체커

# 문제

# 문제 해설 및 코드 리뷰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;


public class Main {
    static boolean flag = false;
     static class Point implements Comparable<Point>{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Point o){
            if(this.y == o.y)
                flag = true;
            return this.y - o.y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Point> queue = new PriorityQueue<>();
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            queue.offer(new Point(i, x - y));
            queue.offer(new Point(i, x + y));
        }
        if(flag) {
            System.out.println("NO");
            System.exit(0);
        }
        while (!queue.isEmpty()) {
            if (stack.isEmpty()) {
                stack.push(queue.poll().x);
            }
            else{
                int t = queue.poll().x;
                if(stack.peek() == t)
                    stack.pop();
                else
                    stack.push(t);
            }
        }
        if (stack.isEmpty()) {
            System.out.println("YES");
        }else
            System.out.println("NO");
    }
}

이전에 활용했던 PriorityQueue를 Comparable인터페이스를 통해 오름차순으로 정리하는 것이 필요한 문제입니다.

지난번에는 PriorityQueue에 들어가는 자료값이 낱개로 들어가서 그것을 오름차순으로 정렬하려고할 때에는 

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o1 - o2);

이렇게 바꾸어서 썼었고 

PriorityQueue<Integer> queue = new PriorityQueue<>((Comparator.comparingInt(o -> o)));

이런식으로 바꾸어서 쓰는 것도 가능했습니다. 

둘 다 오름차순을 의미하는 것이고 람다식을 이용해서 정렬할 수 있다는 것이 우선순위 큐의 장점입니다.

저는 이 문제를 풀기 전에 조금 고민을 했는데, PriorityQueue에 넣을 자료 값이 1쌍이라면 어떻게 하는게 좋을까.. 싶어서 검색을 좀 했습니다.

그랬더니 Comparable인터페이스를 이용해서 하는 것이 좋다 생각하여 Point클래스로 implements하여 로직을 짰습니다.

살펴보겠습니다.

static boolean flag = false;
 static class Point implements Comparable<Point>{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Point o){
        if(this.y == o.y)
            flag = true;
        return this.y - o.y;
    }
}

static으로 boolean타입의 flag를 false로 초기화합니다.

그리고 Point class를 Comparable<Point>로 implements하구요.

이 때에는 Comparable 인터페이스를 이용하면서 int타입의 x, y를 이용하여 오버로딩합니다.

그리고 compareTo메서드를 이용하여 파라미터 Point o를 비교하여 정렬할 수 있는데요.

만약 겹치는 점이 있으면 만나는 교점이 2개여서 굳이 더 실행하지 않아도 되기 때문에 this.y = o.y면 flag = true라 합니다.

그리고 계속해서 this.y - o.y; 이렇게 입력하면 y의 값들에 대해서 오름차순으로 정렬할 수 있게 됩니다.

만약 내림차순으로 정렬하고 싶을때에는 o.y - this.y;라고 입력하시면 내림차순으로 정렬할 수 있게됩니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Point> queue = new PriorityQueue<>();
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < n; i++){
    StringTokenizer st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());
    queue.offer(new Point(i, x - y));
    queue.offer(new Point(i, x + y));
}

입력값이 많으니 Buffer를 이용해서 입력 받습니다.

그리고 항상 문제를 풀기 전에 어떤 자료구조를 이용하면 좋을지 늘 고민을 해보는게 좋습니다.

저같은 경우는 오름차순으로 값을 정렬하고 싶고 가장 속도가 빠른게 뭘까 고민을 해보니 우선순위 큐만한게 없다 생각이 들어서 이걸 이용했습니다.

하지만 대입되는 값이 한 쌍이 될 경우의 인터페이스는 공부가 덜 되어 있어서 다른 분의 자료를 참고해야만 했습니다.

앞으로는 안까먹을 것입니다 ㅎ.

어쨌든 PriorityQueue를 쓰기로 했으면 이 정렬된 우선순위를 가지고 뭘 할꺼냐? 

자 Stack도 전 새로 선언할 것인데요.

queue에는 인덱스와 원의 x - r, x + r지점을 두 번 넣고 (그럼 queue에는 2개의 값이 들어가겠죠) for문으로 n번 반복하겠습니다. (최종적으로 queue에는 2n개가 들어가겠네요)

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

그리고 아까의 flag가 true면 "NO"를 출력하고 종료합니다.

만약 그렇지 않다면

while (!queue.isEmpty()) {
    if (stack.isEmpty()) {
        stack.push(queue.poll().x);
    }
    else{
        int t = queue.poll().x;
        if(stack.peek() == t)
            stack.pop();
        else
            stack.push(t);
    }
}

queue가 비어있지 않을 때에 while문을 돌립니다. 이건 모든 자료구조문의 결이 똑같습니다.

제가 나타내고 싶은 것은 queue에는 2가지의 값이 각각 들어가있을텐데, y의 값인 원의 각각의 x좌표들이 입력되어 있을 것입니다. 

그 y들을 모두 오름차순으로 정렬했을 때 이 x들도 값이 모두 같은지를 보는 것입니다.

무슨말이냐면 만약 y애들을 오름차순 정렬했는데 x애들이 순서가 뒤틀리잖아요?

그럼 이건 원이 교점을 가지고 있다는걸 의미해요.

따라서 while문을 다 마치고 나왔을 때 stack에 비어있어야 YES를 출력할 수 있습니다.

따라서 만약 stack이 비어있을 땐 queue를 빼와서 x를 넣고

비어있지 않을 땐 queue에서 한 번 더 x를 뺴와서 (같은 x가 2개씩 있습니다.)

만약 stack.peek()와 뽑아온 x가 같으면 stack.pop()을 시행하고 아니라면 stack에 x를 한 번 더 넣어버립니다.

그럼 무슨 일이 생기냐면, 원이 모두 서로 내부에 있다 생각해보세요.

아마도 제거되는 stack없이 n번까지는 stack에 계속 push할 것입니다.

그러나 그 이후부터 차례대로 stack의 peek가 queue에서 새로 뽑아오는 x와 같으므로 모두 stack은 없어집니다.

잘 보시면 queue에 들어갈 것은 queue.offer(new Point(0, 1번), queue.offer(new Point(new Point(0,4번)), 2번, 3번순으로 들어가서 졍렬된다면 1,2, 3, 4순으로 정렬될 것입니다.

이것을 토대로 while문을 돌릴 때 stack에는 1번을 넣고 1번과 같은 인덱스가 없으므로 2번이 담기겠죠.

이후 여전히 stack은 비어있지 않으므로 else문을 실행하여 3번이 t가됩니다. 

이 t는 stack.peek()인 2번의 인덱스(2번째 원이므로 x값은 1이겠죠)와 같으므로 stack.pop()하게 되고 마지막으로 1번과 4번도 인덱스가 같으므로 stack.pop()하게 되는 것이랍니다.

최종적으로 내부에 있는 원은 이렇게 해결이 가능하며 외부에 있는 원 또한 스스로 stack에서 데이터 값을 넣었다 뺐다하며 사라지기 때문에 이 과정으로 이해하실 수 있을 것이라 생각듭니다.

최종적으로 stack이 비어있으면 YES, 아니면 NO를 출력하여 정답으로 작성하시면 되겠습니다.

감사합니다.