[백준] 2141 우체국 (Java)

[2141 우체국]

난이도: 골드4

2141번: 우체국

문제

입력

출력

---

[아이디어]

입력할 때 우체국 위치 순서대로 입력한다는 말은 없기 때문에 중간에 정렬을 해줘야한다.

전체 인구 수의 절반 이상이 넘어가면 그 위치가 정답이 된다. 하지만 전체 인구 수가 홀수일 수 있어서 1을 더한 값으로 계산해줘야한다.

---

[JAVA 코드]

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N;
	static long total;
	static Post [] nums;
	
	static class Post implements Comparable<Post> {
		int idx, n;
		
		public Post(int i, int n) {
			this.idx = i;
			this.n = n;
		}

		@Override
		public int compareTo(Post o) {
			if(this.idx == o.idx) {
				return Integer.compare(this.n, o.n);
			}
			return Integer.compare(this.idx, o.idx);
		}
	}
	
	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		nums = new Post [N];
		for(int i = 0; i < N; i++) {
			tokens = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(tokens.nextToken());
			int n = Integer.parseInt(tokens.nextToken());
			
			nums[i] = new Post(idx, n);
			total += n;
		}
		
		Arrays.sort(nums);
		
		long sum = 0;
		for(int i = 0; i < N; i++) {
			sum += nums[i].n;
			
			if(sum >= (total + 1) / 2) {
				System.out.println(nums[i].idx);
				break;
			}
		}
	}
}