외계인의 기타 연주

문제

언어

  • JavaScript

순서도

  1. 간단한 스택 구현 또는 배열 사용
  2. 스택을 이용해서 주어지는 N 개의 기타줄 구현
  3. 주어진 입력에 따라서 스택에 값을 넣고, 빼는 방식을 통해서 기타줄의 누름을 구현하기
  4. 3 번 과정속에서 손가락을 움직이는 횟수 구하기

문제 풀이 step 1

  • 우선 프렛에 대해서 알아보겠습니다. 백준 2841번 외계인의 기타 연주 문제의 프렛 사진
    • 위의 사진에서 은색 부분을 프렛이라고 합니다. 이 부분을 이용하면 기타에서 다양한 음을 연주할 수 있게 해줍니다.
  • 문제는 주어진 입력에 따라서 외계인이 멜로디를 연주하는데 필요한 손가락 움직임의 최소 횟수를 구하는 것입니다.
  • 외계인은 손가락을 수십억개 가지고 있습니다.
    • 사람은 프렛을 누를 때, 손가락의 개수가 한정되어 있기 때문에 이전에 누르고 있는 프렛에서 손가락 떼야 다른 프렛을 누를 수 있습니다.
    • 반면에 외계인은 손가락의 개수가 수십억개이기 때문에 이전에 누르고 있는 프렛에서 손가락을 떼지 않아도 다른 프렛을 누를 수 있습니다.
  • 그리고 구해야 할 것은 손가락 움직임의 최소 횟수입니다.
    • 예를 들어, 3 번 줄의 5 번 프렛을 누르고 있는 상황에서 3 번 줄의 7 번 프렛을 연주하라는 입력이 들어옵니다.
    • 이 때, 굳이 3 번 줄의 5 번 프렛을 누르고 있는 손가락을 뗄 필요 없이 바로 3 번 줄의 7 번 프렛을 누르면 됩니다.
    • 이후에 다시 3 번 줄의 5 번 프렛을 연주하라는 입력이 들어오면 3 번 줄의 7 번 프렛을 떼기만 하면 되니까 손가락을 최소한으로 움직일 수 있습니다.
  • 왼손으로 프렛을 잡고 오른손으로 기타줄을 튕길 때, 중요한 것은 가장 오른쪽에 눌린 프렛만 연주된다는 것입니다.
    • 예를 들어, 2 번, 3 번, 5 번 프렛이 눌려있다고 가정하겠습니다. 이때, 6 번 프렛을 누르고 연주한다면 앞의 2 번, 3 번, 5 번 프렛은 연주하는 음에 어떠한 영향도 끼칠 수 없습니다. 오로지 6 번 프렛만 의미를 가지게 됩니다.
    • 기타줄의 이러한 성질 때문에 스택을 이용하면 수월하게 풀 수 있습니다.
    • 스택에는 가장 최근에 눌린 프렛의 번호가 들어있도록 구현합니다.
    • 그리고 현재 누를 프렛 번호와 스택의 맨 위에 있는 프렛 번호를 비교합니다.
    • 만약 현재 누를 프렛 번호가 더 크다면 바로 스택에 넣어주면 됩니다.
    • 하지만 현재 누를 프렛 번호가 더 작다면 스택에서 현재 누를 프렛 번호보다 큰 프렛 번호들을 다 빼주면 됩니다.
  • 위에서 알아본 성질과 스택을 이용해서 외계인의 손가락의 움직임의 횟수를 구하고 출력하면 정답이 됩니다.
  • 추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 간단한 스택 구현 or 배열 사용
class Stack {
	constructor() {
		this.bucket = [];
		this.top = -1;
	}

	isEmpty() {
		return this.top === -1;
	}

	push(data) {
		this.bucket[++this.top] = data;
	}

	pop() {
		if (!this.isEmpty()) return this.bucket[this.top--];
	}

	peek() {
		return this.bucket[this.top];
	}
}

const solution = (input) => {
	const [n, p] = input[0].split(" ").map(Number);

	const stackArr = Array.from({length: n + 1}, () => new Stack());

	let cnt = 0;
	for (let i = 1; i < n + 1; i++) {
		const [sound, fret] = input[i].split(" ").map(Number);

		// 스택에 비어있지 않다면, 스택에서 현재 누를 프렛 번호보다 큰 프렛 번호들을 제거 (손가락 떼기)
		while (!stackArr[sound].isEmpty() && stackArr[sound].peek() > fret) {
			stackArr[sound].pop();
			cnt += 1;
		}

		// 스택이 비어있거나
		// 스택이 비어있지 않고, 스택에서 현재 누를 프렛 번호와 다르다면 스택에 프렛 번호 넣기 (손가락 누르기)
		// 입력으로 같은 프렛 번호가 들어올 수 있기 때문에 이렇게 처리했습니다.
		if (
			stackArr[sound].isEmpty() ||
			(!stackArr[sound].isEmpty() && stackArr[sound].peek() !== fret)
		) {
			stackArr[sound].push(fret);
			cnt += 1;
		}
	}

	// 손가락의 움직임의 횟수 출력
	return cnt;
};

console.log(solution(input));