[BaekJoon] 2841 외계인의 기타 연주

1.  문제 링크

2.  문제

요약

• 수십억 개의 손가락을 가진 외계인이 1번 줄부터 6번 줄까지 총 6개의 줄이 있고 각 줄이 1번부터 P번까지 P개의 프렛으로 나누어져 있는 기타를 연주하려고 합니다.
• 멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기며 연주하는데 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생합니다.
• 만약 어떤 줄에서 프렛을 이미 누르고 있을 때 더 높은 프렛의 음을 연주하려면 현재 프렛을 누른 상태로 해당 프렛을 누르고 줄을 튕기면 되고 더 낮은 프렛의 음을 연주하려면 잡고있는 프렛 중에서 해당 프렛보다 높은 프렛에서는 손가락을 떼고 해당 프렛을 누른 뒤에 줄을 튕기면 음을 연주할 수 있습니다.
• 이렇게 프렛에서 한 번 손가락을 떼는 행위나 손가락으로 프렛을 한 번 누르는 행위를 손가락을 한 번 움직였다고 합니다.
• 어떤 멜로디가 주어졌을 때 손가락을 가장 적게 움직이는 횟수를 구하는 문제입니다.
• 멜로디로 주어진 음들은 주어진 음의 순서대로 기타를 연주해야 합니다.
• 입력: 첫 번째 줄에 500,000보다 작거나 같은 멜로디에 포함되어 있는 음의 수 N과 2보다 크거나 같고 300,000보다 작거나 같은 프렛의 수 P가 주어지고 두 번째 줄부터 N개의 줄에는 멜로디의 한 음에 대해서 줄의 번호와 그 줄에서 눌러야 하는 프렛의 번호가 주어집니다.
• 출력: 첫 번째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	public int getMinMoveNum(int[][] melody) {
		Stack<Integer>[] frets = new Stack[6];
		int count = 0;
		for(int i = 0; i < frets.length; i++) {
			frets[i] = new Stack<Integer>();
		}
		for(int i = 0; i < melody.length; i++) {
			if(frets[melody[i][0] - 1].size() == 0) {
				frets[melody[i][0] - 1].push(melody[i][1]);
				count++;
			}
			while(frets[melody[i][0] - 1].size() != 0 && frets[melody[i][0] - 1].peek() > melody[i][1]) {
				frets[melody[i][0] - 1].pop();
				count++;
			}
			if(frets[melody[i][0] - 1].size() != 0 && frets[melody[i][0] - 1].peek() == melody[i][1]) {
				continue;
			}
			frets[melody[i][0] - 1].push(melody[i][1]);
			count++;
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int note_num = Integer.parseInt(st.nextToken());
		int fret_num = Integer.parseInt(st.nextToken());
		int[][] melody = new int[note_num][2];
		for(int i = 0; i < melody.length; i++) {
			input = br.readLine();
			st = new StringTokenizer(input);
			melody[i][0] = Integer.parseInt(st.nextToken());
			melody[i][1] = Integer.parseInt(st.nextToken());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMinMoveNum(melody) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 멜로디로 주어진 음들을 주어진 순서대로 연주해야 하기 때문에 주어진 음의 순서를 따라가며 연주하려는 줄에서
• 연주하려는 프렛보다 더 높은 프렛을 잡고 있다면 해당 프렛들을 떼고 연주하려는 프렛을 잡도록 하고
• 잡고 있는 가장 높은 프렛이 연주하려는 프렛보다 더 낮은 프렛이라면 연주하려는 프렛을 바로 잡도록 하며
• 잡고 있는 가장 높은 프렛이 연주하려는 프렛과 같다면 손가락을 움직이지 않도록 하여
• 손가락이 움직이는 횟수를 구하면 됩니다.
• 잡고 있는 프렛을 저장하기 위한 배열이 필요한데 해당 배열에 잡고 있는 프렛을 넣을 때는 가장 높은 프렛이 순서상 더 나중에 들어가기 때문에 이러한 성질을 이용하기 위해 Stack 자료구조를 이용합니다.

1. 각 줄에서 어떤 프렛을 잡고 있는지를 확인하기 위해 6개의 Stack 배열을 만들고 6개의 Stack 배열을 초기화합니다.
2. 손가락이 움지인 횟수를 나타내는 변수인 count를 0으로 초기화합니다.
3. 멜로디로서 주어진 음들을 순서대로 돌면서 해당 위치의 Stack 배열에 프렛들을 추가해갑니다.
• 만약 연주하려는 줄에서 아직 프렛을 잡고 있지 않는다면 연주하려는 프렛을 연주하려는 줄에 저장하고 count를 1 증가시킵니다..
• 연주하려는 줄이 잡고 있는 프렛의 수가 0이 아니고 연주하려는 줄에서 가장 높이 잡고 있는 프렛이 현재 연주하려는 프렛보다 클 때동안 연주하려는 줄에서 가장 높이 잡고 있는 프렛을 Stack에서 빼고 count를 1 증가시킵니다.
• 반복문을 모두 다 돌고 난 후에 가장 높이 잡고 있는 프렛이 현재 연주하려는 프렛과 같다면 다른 작업을 하지 않고 만약 그렇지 않다면 연주하려는 줄에 현재 연주하려는 프렛을 추가하고 count를 1 증가시킵니다.
4. 3번 과정에서 모든 음들을 확인했다면 그 때의 count의 값이 손가락을 최소로 움직인 횟수가 되기 때문에 이를 출력합니다.