[백준/JAVA] BOJ 32358 - 근성아 일하자

TreeSet에 이렇게 좋은 함수들이 있단 말이냐

👀 문제

32358번: 근성아 일하자 ✨ 골드 5

근성은 나무에 관심이 많다.

평소 나무를 깨끗이 관리해 온 근성은 그 능력을 인정받아 북구청 청소행정과에 근무하게 되었다. 어느 날, 민규는 근성을 일하게 하기 위해 나무가 있는 위치에 쓰레기를 버리려고 한다. 나무는 수직선과 같은 일직선상에 있고 근성의 현재 위치는 원점이다. 아래의 두 가지 쿼리를 수행할 때 근성의 총 이동거리를 구하는 프로그램을 작성하시오.

$1$ $x$ : 민규가 정수 좌표 $x$에 있는 나무에 쓰레기를 버린다.
$2$ : 근성은 현재 위치에서 시작하여 쓰레기가 있는 나무 중 가장 가까운 나무로 이동하여 쓰레기를 수거하고, 모든 쓰레기를 수거할 때까지 이 행동을 반복한다. 만약 현재 위치에서 가장 가까운 나무가 두 그루 이상이라면, 좌표가 가장 작은 나무로 이동한다.

예제 입력

7
1 4
1 2
1 -2
2
1 0
2
1 5

예제 출력

12

🔑 키포인트

TreeSet 정렬

✍️ 코드

📍 TreeSet의 floor 와 ceiling 함수를 이용하면 정~말 쉽게 풀 수 있는 문제였다.

💡 정렬을 위해 TreeSet을 이용해서 푸는데, 해당 함수가 존재하는지 몰라서 뻘짓을 좀 했다. 하나 배워갑니다...

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

public class BOJ32358_근성아일하자 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        TreeSet<Integer> ts = new TreeSet<>();
        long answer = 0;
        int guenseong = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            if (type == 1) {
                int idx = Integer.parseInt(st.nextToken());
                ts.add(idx);
            } else {
                // 쓰레기 치우기
                while (!ts.isEmpty()) {
                    Integer left = ts.floor(guenseong); // 가장 가까운 왼쪽 쓰레기
                    Integer right = ts.ceiling(guenseong); // 가장 가까운 오른쪽 쓰래기

                    int target;
                    if (left == null) {
                        target = right;
                    } else if (right == null) {
                        target = left;
                    } else {
                        int leftDistance = guenseong - left;
                        int rightDistance = right - guenseong;
                        if (leftDistance <= rightDistance) {
                            target = left;
                        } else {
                            target = right;
                        }
                    }
                    answer += Math.abs(guenseong - target);
                    guenseong = target;
                    ts.remove(target);
                }
            }
        }
        System.out.println(answer);
    }
}