[JAVA] 네잎 클로버를 찾아서_3089

출처: https://www.acmicpc.net/problem/3089

3089번: 네잎 클로버를 찾아서

 

네잎 클로버를 찾아서 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

212

96

86

53.750%

문제

숭이는 지구에 놀러온 외계인에게 조정당하고 있다. 외계인은 숭이를 이용해서 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 놔두고 다시 자기들의 행성으로 떠나려고 한다. 숭이가 있는 곳은 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 복사

4 4
1 1
1 0
0 1
0 0
RULD

예제 출력 1 복사

0 0

예제 입력 2 복사

7 5
0 0
0 1
0 -1
1 0
1 -1
3 0
3 -1
DRRUD

예제 출력 2 복사

3 -1

예제 입력 3 복사

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

예제 출력 3 복사

1 1

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #2 3번

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 구현
• 자료 구조
• 정렬
• 이분 탐색
• 시뮬레이션

 

 

 

---

import java.util.Scanner;
import java.util.TreeSet;

public class Main
{
    private static Scanner s = new Scanner(System.in);
    
	public static void main(String[] args) {
	    
	    int M = s.nextInt(); // 네잎 클로버의 갯수
	    int N = s.nextInt(); // 외계인의 명령 수
	    
	    // 네잎 클로버 위치 저장
	    // X, Y별로 배열을 만들어 각 X에 대한 Y의 값 / 각 Y에 대한 X의 값 셋 저장
	    // 빠른 검색을 위해 TreeSet 사용
	    TreeSet<Integer>[] xSet = new TreeSet[200000]; // 문제에서 -100,000~100,000 이랬으므로 200,000
	    TreeSet<Integer>[] ySet = new TreeSet[200000];
	    
	    for(int i=0; i<M; i++) {
	        int x = s.nextInt() + 100000; // 시작 포인트가 -100,000이므로 더해야 함. (안그러면 ArrayIndexOutOfBound에러)
	        int y = s.nextInt() + 100000;
	        
	        if(xSet[x] == null) {
	            xSet[x] = new TreeSet<>();
	        }
	        if(ySet[y] == null) {
	            ySet[y] = new TreeSet<>();
	        }
	        
	        xSet[x].add(y);
	        ySet[y].add(x);
	    }
	    
	    // 외계인이 보낸 명령어 저장
	    String command = s.next();
	    
	    // 현재 위치 저장 : 초기값은 0, 0
	    int locX = 100000; // 마찬가지로 시작점이 -100000으로 가정
	    int locY = 100000;
	    
	    // 커멘드에 따른 동작 수행
	    for(int i=0; i<command.length(); i++) {
	        char com = command.charAt(i);
	        
	        switch(com) {
	            case 'U': 
	                // 위 : x가 같고 y가 보다 큰 것 검색
	                locY = xSet[locX].higher(locY);
	                break;
	            case 'D': 
	                // 아래 : x가 같고 y가 보다 작은 것 검색
	                locY = xSet[locX].lower(locY);
	                break;
	            case 'L':
	                // 왼쪽 : y가 같고 x가 보다 작은 것 검색
	                locX = ySet[locY].lower(locX);
	                break;
	            case 'R':
	                // 오른쪽 : y가 같고 x가 보다 큰 것 검색
	                locX = ySet[locY].higher(locX);
	                break;
	        }
	    }
	    
	    locX -= 100000;
	    locY -= 100000;
	    
	    System.out.println(locX + " " + locY);
	}
}