[JAVA]백준 2841번: 외계인의 기타 연주

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

2841번: 외계인의 기타 연주

 

1. 문제 설명

 

문제

• 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다.
• 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.
• 손가락으로 프렛을 한번 누르거나 때는 것을 손가락을 한번 움직였다고 한다.
• 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 횟수를 구하자.

조건

• 음의 수 N(N<=500,000), 한 줄에 있는 프렛의 수 P(2 <=P <=300,000)

 

2. 풀이

 

Stack을 사용해서 풀 수 있다.

 

현재 음을 내려는 프렛보다 큰 프렛들은 제거하고, 현재 줄에서 잡고 있는 프렛이 현재 음을 내려는 프렛보다 작으면 현재 음을 내려는 프렛을 누르면 된다.

 

우선순위 큐, 정렬 등을 사용하지 않아도 위의 로직을 사용하기에 자동적으로 stack은 작은 프렛 순서대로 저장되게 된다.

 

*로직

1. 현재 줄에서 음을 내려는 프렛보다 큰 프렛들을 잡고 있다면 손을 다 뗀다.

2. 그 후, 현재 줄에서 잡고 있는 프렛이 없거나, 현재 줄에서 잡고 있는 프렛이 음을 내려는 프렛보다 작다면 음을 내려는 프렛을 잡는다.

 

3. 코드

// JAVA 11 , 메모리 : 14244KB, 시간 : 132ms

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

public class Main {

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

        int musicNum, fret = 0;
        int move = 0;
        int nowLine, nowFret;

        Stack<Integer>[] stack = new Stack[7];

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

        musicNum = Integer.parseInt(st.nextToken());
        fret = Integer.parseInt(st.nextToken());

        for (int x = 0; x <= 6; x++) {
            stack[x] = new Stack<Integer>();
        }

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

            nowLine = Integer.parseInt(st.nextToken());
            nowFret = Integer.parseInt(st.nextToken());

            // 현재 프렛보다 크면 손 똄
            while(!stack[nowLine].isEmpty() && stack[nowLine].peek() > nowFret ){
                stack[nowLine].pop();
                move++;
            }

            //  현재 줄 에서 잡은 프렛이 없거나 현재 줄에서 잡은 프렛이 현재 프렛보다 작을 경우 프렛을 새로 잡음
            if (stack[nowLine].isEmpty() || stack[nowLine].peek() < nowFret) {
                stack[nowLine].push(nowFret);
                move++;
            }


        }

        bw.write(String.valueOf(move));
        bw.flush();


    }


}