문제

https://www.acmicpc.net/problem/1417

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    LinkedList<Integer> queue = new LinkedList<>();
    int dasom = Integer.parseInt(br.readLine());
    for (int i = 0; i < n-1; i++) {
        int input = Integer.parseInt(br.readLine());

        if (dasom <= input) {
            queue.offer(input);
        }
    }

    Collections.sort(queue);

    int answer = 0;
    for (; !queue.isEmpty() && queue.peekLast() >= dasom; answer++) {
        if (queue.peek() < dasom) {
            queue.poll();
        }

        queue.offer((queue.pollLast()-1));
        dasom++;

        Collections.sort(queue);
    }

    System.out.println(answer);
}

흐름

  1. 다솜이는 기호 1번이므로 첫 번째 입력을 다솜이의 표로 저장한다.
  2. 우선순위 큐로 사용하기 위해 list에 입력들을 저장하는데 다솜이 보다 작을 경우엔 문제의 답과 상관이 없으므로 다솜이의 표보다 적은 표는 큐에 저장하지 않는다.
  3. 우선순위 큐로서 동작하게 하기 위해 반복 전에 큐를 한번 정렬시켜준다.
  4. 그 후엔 큐가 비거나, 큐의 가장 큰 값이 다솜이가 될 때까지 반복한다.
  5. 반복하면서 큐의 맨 앞이 다솜이보다 작다면, 이제 그 사람은 다솜이가 재낀 것 이므로 큐에서 빼주고,
  6. 제일 표가 많은 놈한테서 표 하나를 뻇어서 다솜이가 가져가면 되므로 큐의 마지막 값에서 -1 빼서 다시 큐에 넣어준다.
  7. 그리고 제일 표가 많은 놈에게 뺏은 표를 다솜이에게 줬으므로 다솜이의 값을 1 증가시키고
  8. 우선순위 큐 처럼 동작 할 수 있게 큐를 다시 정렬 시킨다.
  9. 반복된 횟수를 출력하면 끝.

결과

여담

반복문에서 소팅을 하기 때문에 시간 초과가 날 것으로 예상했는데 수가 적은 문제라 그런지 무사히 통과되어 참 다행이다…