[백준]2262: 토너먼트 만들기 - JAVA

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

 

풀이

n명의 선수들의 랭킹이 주어진다. 2명씩 대결을 붙여 우승자를 가리는 토너먼트를 만들어야 한다.

 

1. 랭킹이 가장 낮은 선수를 찾는다.

2. 해당 선수의 좌, 우를 살펴 차이가 적게나는 사람과 대결을 한다.

3. 선수가 1명 남을때까지 반복한다.

 

위의 과정으로 풀 수 있었다.

 

예제에는 `1 6 2 5 3 4` 로 주어졌다.

 

첫 번째로 6을 골라 양 옆에 있는 1과 2 중 2를 선택하여 대결한다.

 

`1 2 5 3 4`가 되고, 같은 방식으로 5를 골라 3과 대결한다.

 

1 6 2 5 3 4 -> 6 vs 2 (4)

1 2 5 3 4 -> 5 vs 3 (2)

1 2 3 4 -> 4 vs 3 (1)

1 2 3 -> 3 vs 2 (1)

1 2 -> 2 vs 1 (1)

 

위 과정으로 진행되고 정답은 9가 된다.

 

---

 

메모리: 14088KB
시간: 100ms
언어: Java 11

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

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<>(Collections.reverseOrder());
        ArrayList<Integer> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int rank = Integer.parseInt(st.nextToken());
            pq.add(rank);
            list.add(rank);
        }

        int answer = 0;
        while (pq.size() > 1) {
            int max = pq.poll();
            int idx = list.indexOf(max);

            int left = idx > 0 ? list.get(idx - 1) : 0;
            int right = idx < list.size() - 1 ? list.get(idx + 1) : 0;

            answer += (max - Math.max(left, right));
            list.remove(idx);
        }

        System.out.println(answer);
    }

}