2841 - 외계인의 기타 연주 (Java)

 

---

 

문제

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

 

 

풀이

맵과 우선순위큐를 활용해서 풀었다.

 

(근데 우선순위큐 말고 스택 쓰는게 2억배는 맞는 접근이다.)

 

Map 의 Key 는 기타줄로 하고, Value 를 플랫을 넣고 관리하는 우선순위 큐로 만든다.

 

플랫 같은 경우에는 같은 줄일때, 더 높은 플랫이 나오면 손가락을 추가(?)만 해주면 된다. (우선순위 큐에 플랫을 추가해주면 된다.)

 

단 낮은 플랫일 경우에는 입력으로 들어온 플랫보다 큰 값이 같은 줄에 있으면 안된다.

따라서 우선순위 큐의 가장 큰 값을 보고 비교해본다음, 우선순위 큐의 가장 큰 값이 입력값보다 같거나 작을 때 까지 값을 빼준다.

 

그 다음이 중요한데, 같은 값인 경우에는 손가락을 추가해줄 필요가 없다. 이미 플랫을 짚고 있는 손가락인 경우에는 우선순위 큐에 넣어줄 필요가 없다. 단 그런 경우가 아니라면 추가해주면 된다.

 

코드

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

public class Main {

    public static Map<Integer, PriorityQueue<Integer>> melodys = new HashMap<>();
    public static Long answer = 0L;

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 초기화
        for (int i = 0; i < 6; i++) {
            PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
            melodys.put(i + 1, pq);
        }

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

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

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

            int currentMelody = Integer.parseInt(st.nextToken());
            int currentFlat = Integer.parseInt(st.nextToken());

            while (!melodys.get(currentMelody).isEmpty() && melodys.get(currentMelody).peek() > currentFlat) {
                melodys.get(currentMelody).poll();
                answer++;
            }

            if(!melodys.get(currentMelody).isEmpty()){
                if (melodys.get(currentMelody).peek() == currentFlat){
                    continue;
                }
            }

            melodys.get(currentMelody).add(currentFlat);
            answer++;

        }

        System.out.println(answer);
    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

}

 

후기

 

- 이건 스택을 써서 풀면 된다. 이거 직전에 풀었던 문제랑 굉장히 유사한데, 왜 난 스택을 사용안하고 풀었는가