[백준/JAVA] 2141번: 우체국

📖 문제

2141번: 우체국

 

 

 

💡  풀이 방식

• 정렬 + 그리디 + 중간값

 

우체국 위치와, 마을 거주 인원을 저장하는 마을 객체를 만든다.마을 객체 배열에 값을 입력받고, 모든 마을의 인원 수를 저장한다.

 

입력받은 마을 객체 배열을 정렬한다.

- 서로 거리가 같은 경우, 마을 인원 수 기준 오름차순 정렬

- 서로 거리가 다르다면, 거리 기준 오름차순 정렬

 

그리고 완전탐색을 통해 하나씩 인구 수를 계산하며 중간값과 가장 근접한 마을 찾아 출력한다.

long sum = 0;
        
for(Node now : arr) {
    sum += now.a;

    if(sum >= (result + 1) / 2) {	// 중간값과 비교
        System.out.println(String.valueOf(now.x));
        break;
    }
}

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static Node[] arr;
    static long result = 0; // 총 인원
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());    // 마을 수
        arr = new Node[N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            long X = Long.parseLong(st.nextToken());
            long A = Long.parseLong(st.nextToken());
            arr[i] = new Node(X, A);
           result += A; // 총 인원 구하기
        }
        
       Arrays.sort(arr); // 마을 위치 기준 오름차순 정렬
        
        long sum = 0;
        
        // 하나씩 인구 수 계산해 "중간값과 가장 근접한 마을" 찾아 출력하기
        for(Node now : arr) {
            sum += now.a;
            
            if(sum >= (result + 1) / 2) { // 중간값 : (result + 1) / 2
                System.out.println(String.valueOf(now.x));
                break;
            }
        }
    }
}
 
class Node implements Comparable<Node> {
    long x, a;
    
    public Node(long x, long a) {
        this.x = x;
        this.a = a;
    }
    
    @Override
    public int compareTo(Node n) {
        // 서로 거리가 같은 경우, 마을 인원 수 기준 오름차순 정렬
        if(this.x == n.x)
            return (int)(this.a - n.a);
        return (int)(this.x - n.x); // 서로 거리가 다르다면, 거리 기준 오름차순 정렬
    }
}
 

 

 

 

➕ 다른 풀이 방식

이분 탐색을 활용한 풀이!

[Java] 백준 2141번 우체국

---

💦 어려웠던 점

- 거주 인원 기준 정렬하고, 사람이 가장 많이 사는 마을에 설치하려고 했었다.

- 중간값이 정답이겠단 생각은 했는데 이걸 구하는 아이디어를 생각하지 못 했다.

 

 

🧐 새로 알게 된 내용

- 정렬하고 나서 완전탐색을 통해 앞에 있는 값부터 순차적으로 인구 수를 더해가면서 중간값과 가장 근접한 마을을 찾아 출력하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[JAVA]백준_2141_우체국

 

[백준, Java] 2141번, 우체국(그리디)