[99클럽 24일차] [백준] 1417 국회의원 선거

[백준] 1417 국회의원 선거

문제 설명

• 첫째 줄 : 후보 수 N (1 ≤ N ≤ 50)

• 둘째 줄부터 : 각 후보를 찍으려는 사람 수

  • 첫 번째 줄: 다솜이를 찍으려는 사람 수
  • 나머지 줄: 다른 후보를 찍으려는 사람 수

• 다솜이가 당선되기 위해 매수해야 하는 최소 인원을 출력해야한다.

첫번째 코드 작성과 문제점

첫번째 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

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

        int max = Integer.MIN_VALUE;
        int count = 0;

        while (dasom > max) {
            max = pq.poll();
            dasom++;
            max--;
            pq.offer(max);
            count++;
        }

        bw.write(String.valueOf(count));

        bw.flush();
        bw.close();
        br.close();
    }
}

문제점 분석

• 후보자가 다솜 혼자일 경우 매수할 필요가 없다. 이 조건을 처리해서 불필요한 연산 및 Index가 음수가 되는 것을 피해야한다.
• dasom > max 조건과 PriorityQueue에서 감소된 값을 다시 삽입하는 로직이 제대로 종료되지 않을 수 있다. 음수 값이 PriorityQueue에 계속 삽입되면서 무한 루프 가능성이 생긴다.
• int max = Integer.MIN_VALUE;로 설정했다. 하지만 PriorityQueue.poll()과 충돌하거나 초기 비교에서 논리가 깨질 가능성이 있으므로 max값을 바로 poll해서 초기화 해야한다.

수정된 정답 코드

import java.io.*;
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());
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        
        int dasom = Integer.parseInt(br.readLine());
        for (int i = 0; i < N - 1; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }

        if (N == 1) {
            System.out.println(0);
            return;
        }

        int count = 0;

        while (!pq.isEmpty() && pq.peek() >= dasom) {
            int max = pq.poll();
            max--;
            dasom++;
            pq.offer(max);
            count++;
        }

        System.out.println(count);
    }
}

결론

무한 루프 조건 처리/ 단일후보 (다솜이만 선거에 나옴) 처리를 누락했기 때문에.. 두번의 실수가 있었다. 문제를 꼼꼼히 읽고 조건을 처리하는 것이 중요하다.

• index가 음수가 되는 부분 ⭐️⭐️⭐️
• 불필요하게 loop를 도는 부분 ⭐️⭐️⭐️

Collections.reverseOrder() VS 람다

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);와 PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());는 속도면에서 거의 동일한 성능을 보인다.
그러므로 기본 역순 정렬할때는 reverseOrder, 다른 조건이 있는 정렬을 할 때는 람다를 사용하면 좋을 것이다 !!