[백준] 2141 - 우체국 | Java

📌 문제 정보

[2141번: 우체국]

---

💡 접근 방식

위치와 인구 수를 저장하는 TreeMap을 만들고, 전체 탐색을 하면서 해당 위치에서의 이동 인구수와 위치를 저장하는 TreeMap을 만들었다.
결과는 시간초과~!

찾아야 하는 것은 사람들이 가장 적게 걸어야 하는 위치이다.
즉, 누적 인구가 전체 인구의 절반을 처음으로 넘는 위치를 찾아야 한다.

---

🧪 시도한 풀이

시간초과 발생

import java.util.*;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        TreeMap<Long, Long> map = new TreeMap<>();
        TreeMap<Long, Long> people = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Integer.parseInt(st.nextToken());
            long a = Integer.parseInt(st.nextToken());

            map.put(x, a);

        }

        for (long i : map.keySet()) {
            long sum = 0;

            for (long j : map.keySet()) {
                if (j != i) {
                    sum += map.get(j);
                }
            }
            people.putIfAbsent(sum, i);
        }

        System.out.println(people.firstEntry().getValue());

    }

}

---

✅ 최종 풀이

import java.util.*;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long totalPeople = 0;
        TreeMap<Long, Long> map = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Integer.parseInt(st.nextToken());
            long a = Integer.parseInt(st.nextToken());

            map.put(x, a);

            totalPeople += a;
        }
        
        long mid = (totalPeople + 1) / 2;

        long sum = 0;
        for (Long l : map.keySet()) {
            sum += map.get(l);

            if (sum >= mid) {
                System.out.println(l);
                return;
            }
        }
    }

}

---

🧠 배운 점 & 회고

중앙값이 되는 시점이 아니라 중앙값을 넘는 시점을 찾아야 한다.
누적 인구 >= (총 인구 + 1) / 2

• 짝수일 땐 절반 이상이 되는 시점
• 홀수일 땐 반올림한 절반 이상이 되는 시점

처음엔 이 점을 생각하지 못하고 중앙값이 되는 시점을 찾았다.

if (totalPeople % 2 == 1) {
    mid = (totalPeople - 1) / 2;
} else {
    mid = totalPeople / 2;
}

이렇게 계산하니 절반 기준이 낮게 잡혀서 적절하지 않은 위치가 선택되었던 거였다.

---

🧾 결과