[BOJ] 1417번 국회의원 선거

💡 내가 푼 풀이

• arrayList에 다솜보다 크거나 같은 득표수 넣기
• 오름차순 정렬 후 맨 마지막에 있는 값이 다솜보다 작으면 break, 크면 값 1 감소, count 1 증가
• 다솜보다 작은 원소는 제거

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<Integer>();

		int first = Integer.parseInt(br.readLine());
		for (int i = 0; i < n - 1; i++) {
			int input = Integer.parseInt(br.readLine());
			if (first <= input)
				list.add(input);
		}

		int count = 0;

		while (!list.isEmpty()) {
			Collections.sort(list);
			int size = list.size();
			if (list.get(size - 1) < first) {
				break;
			}
			first++;
			list.set(size - 1, list.get(size - 1) - 1);
			count++;
			for (int i = size - 1; i >= 0; --i) {
				if (first > list.get(i)) {
					list.remove(i);
				}

			}
		}

		System.out.println(count);

	}
}

💡 큐 이용한 풀이

• MaxHeap에 다솜을 제외한 득표수 넣기
  -> Collections.reverseOrder() 사용
• heap에서 꺼낸 값이 다솜이보다 크거나 같으면 그 득표수 감소 시킨 후에 큐에 넣기
• 다솜 득표수 증가, count 증가

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;

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

		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

		for (int i = 0; i < n - 1; i++) {
			pq.add(Integer.parseInt(br.readLine()));
		}

		int count = 0;
		while (!pq.isEmpty() && pq.peek() >= first) {
			first += 1;
			count += 1;
			pq.add(pq.poll() - 1);
		}

		System.out.println(count);

	}
}