[백준] 23326 홍익 투어리스트 (Java)

[23326 홍익 투어리스트]

난이도: 골드3

23326번: 홍익 투어리스트

문제

입력

출력

---

[아이디어]

구현이 중요한 문제같다.

TreeSet을 활용하여 명소의 위치를 관리해주었는데, 이 이유는 3번 쿼리를 빠르게 다루기 위해서이다.

 

처음에 명소의 위치를 초기화해준 후 쿼리문을 수행하는데, 1번 쿼리는 단순히 set에 넣고 빼주기만 하면 된다.

2번 쿼리는 위치를 이동시켜주는데 now = (now + n - 1) % N + 1 이 식을 활용하면 된다.

이 때, now의 최대 값은 5십만이고 n 이 최대 10억이기 때문에 int의 범위를 벗어나지 않는다.

 

가장 시간 초과가 나기 쉬운 부분이 3번 쿼리문이다.

우선 set이 비어있다면 명소에 도달할 수 없기 때문에 -1을 출력해준다. 또한, 현재 위치가 명소에 들어있다면 0을 출력한다. 그 다음 시계방향에서 가장 가까운 명소를 찾는 방법인데, 나는 TreeSet에 있는 함수인 ceiling()을 활용하였다.

ceiling(num) 은 num이상의 수들 중 가장 작은 수를 반환하고, 없다면 null을 반환하는 함수이다.

이 함수로 현재 위치보다 큰 번호의 명소를 찾아 거리의 차이(idx - now)를 계산해주었고, 없다면 명소 중 가장 작은 번호의 명소로 차이(N - now + spots.first())를 계산해주었다.

 

---

[JAVA 코드]

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int N, Q, now;
	static TreeSet<Integer> spots = new TreeSet<>(); // 명소 위치 저장

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		Q = Integer.parseInt(tokens.nextToken());
		
		tokens = new StringTokenizer(br.readLine());
		for(int i = 1; i <= N; i++) {
			if(Integer.parseInt(tokens.nextToken()) == 1) spots.add(i);
		}
		
		// 현재 위치 초기화
		now = 1;
		for(int t = 0; t < Q; t++) {
			tokens = new StringTokenizer(br.readLine());
			
			switch(tokens.nextToken()) {
			case "1":
				// n번 구역 명소 지정 또는 지정x
				int n = Integer.parseInt(tokens.nextToken());
				if(spots.contains(n)) spots.remove(n);
				else		 		  spots.add(n);
				break;
			case "2":
				// n만큼 이동하기
				n = Integer.parseInt(tokens.nextToken());
				now = (now + n - 1) % N + 1;
				break;
			case "3":
				if(spots.isEmpty()) {
					// 명소가 없는 경우
					output.append("-1\n");
				} else if(spots.contains(now)) {
					// 지금 위치가 명소인 경우
					output.append("0\n");
				} else {
					// 지금 위치보다 큰 인덱스 중 현재 위치와 가장 가까운 인덱스
					Integer idx = spots.ceiling(now);
					if(idx != null) {
						// 오른쪽에 명소가 존재하는 경우
						output.append((idx - now) + "\n");
					} else {
						// 오른쪽에 없으면 가장 작은 명소의 위치로 계산
						output.append((N - now + spots.first()) + "\n");
					}
				}
				break;
			}
		}
		System.out.println(output);
	}

}