[백준] 29160 : 나의 FIFA 팀 가치는?

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

29160번: 나의 FIFA 팀 가치는?

 

문제를 보자마자 떠올렸던 방식은

1. 포지션 번호가 11개니 총 11개의 List<Integer>를 만들기

2. K년동안 List를 Sort하여 마지막 원소값을 빼주기

3. List 재정렬

4. List의 마지막 원소값을 모두 더해 정답 출력

 

이대로 코드를 짜다보니 11개의 List를 만들고있는 순간 현타가 와서 다시 고민했다. (이건 너무 하드 코딩이잖아;;)

 

두가지에 대해 고민하였다.

 

1. 정렬을 안할 방법이 있을까?

2. 11개의 List를 만드는건 너무 귀찮다. 쉽게 관리할 수 없을까?

 

이 두가지에 대해 고민하다가 나온 결론은 

 

1. 정렬을 안 할 방법이 있을까? -> 우선순위 큐 사용하기

2. 11개의 List를 만드는건 너무 귀찮다. 쉽게 관리할 수 없을까? -> Map 사용하기

 

이렇게 Map과 우선순위 큐(Priority Queue)를 이용하면 코드 길이도 확 줄어들고 정렬을 직접 할 필요가 없다 👍

 

나는 총 11개의 포지션 번호를 관리하기 위해 아래와 같이 초기화 하여 사용하였다.

 

이 때, PriorityQueue는 default로 오름차순을 사용하기에 peek()을 했을 때 큐 내의 최소값을 반환하기 때문에 Collections.reversOrder()를 사용하여 내림차순으로 정렬하게 만들었다.

Map<Integer, PriorityQueue<Integer>> team = new HashMap<>();

for (int i = 1; i <= 11; i++) {
    team.put(i, new PriorityQueue<>(Collections.reverseOrder()));
}

 

나의 풀이

 

package problem;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Problem_29160 {
    static StringTokenizer st;
    static int totalValue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());

        Map<Integer, PriorityQueue<Integer>> team = new HashMap<>();

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= 11; i++) {
            team.put(i, new PriorityQueue<>(Collections.reverseOrder()));
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            int position = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            team.get(position).add(value);
        }

        for (int i = 0; i < k; i++) {
            for (int j = 1; j <= 11; j++) {
                Integer maxValue = team.get(j).peek();
                if (maxValue == null) {
                    continue;
                }
                if (maxValue != 1) {
                    team.get(j).poll();
                    team.get(j).add(maxValue - 1);
                }
            }
        }

        for (int i = 1; i <= 11; i++) {
            Integer maxValue = team.get(i).peek();
            if (maxValue != null) {
                totalValue += maxValue;
            }
        }

        System.out.println(totalValue);
    }
}

 

https://github.com/SungchoonPark/baekjoon/blob/main/src/problem/Problem_29160.java