[JAVA] 백준 23326번 【G3.홍익 투어리스트】

문제

23326번: 홍익 투어리스트

---

풀이

1️⃣ treeSet을 이용한 풀이

💡 떠오른 Idea

구역의 개수가 500000 이고 쿼리의 개수가 100000 이므로

선형탐색을 하게되면 시간복잡도가 최대 500000*100000 으로 절대 통과 못하는 수치가 나온다.

따라서, treeSet을 이용한 풀이가 필요하다.

treeSet의 대부분의 메서드는 log(N) 의 성능으로 동작하기 때문이다.



treeSet에 명소 번호를 갱신하고, 쿼리문을 수행하면서 도현이의 위치도 갱신한다.

만약 도현이와 가장 가까운 위치의 명소 번호를 찾는 과정은,

시계 방향 기준 최소 거리를 구하는 것이므로, treeSet 안에 도현이의 위치보다 크거나 같은 명소를 먼저 탐색해본다. (ceiling 메서드 사용)

만약 도현이보다 크거나 같은 명소가 없다면 treeSet의 제일 앞 원소가 가장 가까운 명소가 될 것이다.

도현이보다 번호 상 앞에 있는 명소와의 거리를 구할때에는 ( N - dohyun + 명소) 로 구해준다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]), Q = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        
        // 명소 등록
        TreeSet<Integer> places = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            if (input[i].equals("1")) {
                places.add(i + 1);
            }
        }

        int doHyun = 1;
        StringBuilder ans = new StringBuilder();
        
        // 쿼리 수행
        while (Q-- > 0) {
            input = br.readLine().split(" ");
            if (input[0].equals("3")) {
                Integer ceiling = places.ceiling(doHyun);

                int distance = 0;
                
                // 도현이 위치 뒤에 명소가 없는 경우 (rotate 필요)
                if (ceiling == null) {
                    
                    // 명소가 있는 경우
                    if (!places.isEmpty()) {
                        ceiling = places.first();
                        distance = N - doHyun + ceiling;
                    // 명소가 아예 없는 경우    
                    } else {
                        distance = -1;
                    }
                } else {
                    // 도현이 뒤에 명소가 존재하는 경우
                    distance = ceiling - doHyun;
                }

                ans.append(distance + "\n");


            } else {
                int num = Integer.parseInt(input[1]);

                // 명소 추가 혹은 변경
                if (input[0].equals("1")) {
                    if (places.contains(num)) {
                        places.remove(num);
                    } else {
                        places.add(num);
                    }
                // 도현이 이동    
                } else {
                    doHyun = (doHyun + num) % N;
                    if (doHyun == 0) {
                        doHyun = N;
                    }
                }
            }
        }

        System.out.println(ans);

    }
}

---

📖 회고

이번 문제를 풀면서, treeSet의 동작 원리를 잘 파악할 수 있었다.

 

특히, 특정 값보다 크거나 같은 값을 찾는 ceiling 메서드와

 

특정 값보다 작거나 같은 값을 찾는 floor 메서드를 알게 되었다.