[백준]#3089 네잎 클로버를 찾아서

문제

숭이는 지구에 놀러온 외계인에게 조정당하고 있다. 외계인은 숭이를 이용해서 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 놔두고 다시 자기들의 행성으로 떠나려고 한다. 숭이가 있는 곳은 2차원 평면으로 나타낼 수 있고, 클로버는 N개의 점으로 나타나 있다.

숭이의 절친한 친구인 희웅이와 태완이는 숭이를 찾아 다시 정신을 차리게 해주려고 한다. 숭이는 맨 처음에 (0, 0)에 있고, 외계인은 그에게 명령을 M번 전송한다. 각 명령은 네 방향 중 하나이며, 숭이는 그 방향으로 가장 가까운 네잎 클로버가 있는 곳까지 걸어간다.

네잎 클로버의 위치와 외계인이 전송한 명령이 주어졌을 때, 모든 명령을 수행한 뒤에 숭이가 있는 곳의 위치를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 네잎 클로버의 개수 N과 외계인이 전송한 명령의 수 M이 주어진다. (3 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)

다음 N개 줄에는 네잎 클로버의 위치 Xi, Yi가 주어진다. (-100,000 < Xi, Yi < 100,000) 한 위치에 두 개 이상의 네잎 클로버가 있는 경우는 없다.

마지막 줄에는 외계인이 숭이에게 내린 명령이 주어진다. 왼쪽 방향은 L, 오른쪽은 R, 위는 U, 아래는 D로 주어진다. 항상 주어지는 방향에는 네잎 클로버가 있다.

출력

숭이의 마지막 위치를 출력한다.

예제 입력 1

10 6
0 0
1 1
2 1
0 2
-1 2
-1 3
2 3
2 4
4 3
2 -1
ULURDL

예제 출력 1

1 1

풀이

이 문제는 Java 라이브러리에 있는 TreeSet을 이용해서 풀 수 있었다.

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

public class Main {
    static TreeSet<Integer>[] X;
    static TreeSet<Integer>[] Y;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        X = new TreeSet[200000];
        Y = new TreeSet[200000];
        for(int i=0; i<200000; i++) {
            X[i] = new TreeSet<>();
            Y[i] = new TreeSet<>();
        }

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        for(int i=0; i<N; i++) {
            input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            x += 100000;
            y += 100000;

            X[x].add(y);
            Y[y].add(x);
        }

        String command = br.readLine();
        sol(command);
    }

    public static void sol(String command) {
        int x = 100000;
        int y = 100000;

        for(int i=0; i<command.length(); i++) {
            char temp = command.charAt(i);

            if(temp=='U') {
                y = X[x].higher(y);
            }

            else if(temp=='L') {
                x = Y[y].lower(x);
            }

            else if(temp=='R') {
                x = Y[y].higher(x);
            }

            else {
                y = X[x].lower(y);
            }
        }

        System.out.println((x-100000)+" "+(y-100000));
    }
}