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

문제

외계인의 기타 연주

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

 

 

풀이

설명

멜로디를 연주하는데 필요한 최소 손가락 움직임을 구하는 문제입니다.

 

주의해야 할 점은 다음과 같습니다.

1. 기타는 1번부터 6번 줄까지 있습니다.
2. 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생합니다.
3. 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 합니다.

 

스택을 이용해 해결할 수 있습니다.

 

스택에는 해당 줄에서 누르고 있는 프렛들이 들어있습니다.

 

멜로디가 입력되면 다음 과정을 수행합니다.

1. 멜로디의 줄이 처음 연주됐다면 스택에 프렛을 추가합니다.
2. 아니라면 스택에서 멜로디의 프렛보다 높은 프렛은 모두 제거합니다.
   1. 멜로디의 프렛을 이미 누르고 있지 않다면, 스택에 추가합니다.

 

예시 코드

function solution() {
  const TOTAL_STRINGS = 6;
  const [n, p] = input().split(" ").map(Number);
  const stacks = Array.from({ length: TOTAL_STRINGS + 1 }, () => []);
  let fingerMoves = 0;

  for (let i = 0; i < n; i++) {
    const [string, fret] = input().split(" ").map(Number);
    const stack = stacks[string];

    if (!stack.length) {
      stack.push(fret);
      fingerMoves++;
    } else {
      while (stack.at(-1) > fret) {
        stack.pop();
        fingerMoves++;
      }
      if (stack.at(-1) !== fret) {
        stack.push(fret);
        fingerMoves++;
      }
    }
  }

  return fingerMoves;
}