[JavaScript] 백준 2841 외계인의 기타 연주 (JS)

외계인의 기타 연주

📚 문제 설명

N 개의 기타줄이 있고 각각의 기타줄에는 P 개의 프렛이 있다.
그리고 한 개의 줄에 여러개의 프랫을 누르고 있다면, 가장 높은 프렛의 음이 연주된다.
ex - 2번줄에 5프렛 8프렛 2개가 눌려있으면 8프렛이 연주됨.

위의 조건에서 연주해야 할 음이 주어질 때
해당 연주에서 손가락을 최소로 움직이면 몇번 움직이는가.

👨🏻‍💻 풀이 과정

각각의 줄에서 연주될 프렛의 경우 스택을 이용하여 생각하면 편할 것 같다.
예를 들어 Monotonic Stack 을 이용하여 오름차순으로 정렬을 진행하면 스택의 최상단이 내가 연주할 음이 될 것이다.
그런데 줄이 N 개가 주어진다. 따라서 객체를 이용해 {N번줄 : [배열]} 형식으로 각각의 줄에 스택을 만들어 주면 된다.

전체 로직을 간략히 표현하면 다음과 같다.

• 객체를 이용해 각각의 줄에 스택을 만들어 준다.
• 스택에 값을 넣기 전에 스택의 최상단과 내가 넣어줄 값을 비교한다.
  • 만약 내가 넣을 값이 더 작으면
    • 넣을 값보다 큰 값을 스택에서 제거.
  • 그게 아니고 만약 스택의 최상단과 같은 값이 아니라면 스택에 push.
  • 만약 스택이 비어있다면, 스택에 값을 넣어서 값 부여.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, P] = input.shift().split(' ').map(Number);
    input = input.map(v => v.split(' ').map(Number));
    let cnt = 0;
    let Finger = {};

    for (const inputItem of input) {
        const [LINE, PRET] = inputItem;
      	// 만약 스택이 있다면
        if (Finger[LINE]) {
            while (Finger[LINE].length) {
              // 스택의 최상단과 비교 후, pop 진행
                if (Finger[LINE][Finger[LINE].length - 1] > PRET) {
                    cnt++
                    Finger[LINE].pop();
                } else break;
            }
          	// 만약 스택의 최상단 값이 넣어줄 값과 같다면 넘어감
          	// 그게 아니라면 스택에 값을 넣어줌
            if (Finger[LINE][Finger[LINE].length - 1] !== PRET) {
                cnt++;
                Finger[LINE] = [...Finger[LINE], PRET];
            }
          // 만약 스택이 없다면, 스택을 만들어줌
        } else {
            cnt++;
            Finger[LINE] = [PRET];
        }
    }
    console.log(cnt);

🧐 후기

객체에 부여한 스택에 push 하는 부분을 어떻게 만들지하는 고민 때문에 좀 생각이 많았던 것 같다.
그냥 객체[키]를 이용하여 값을 불러온 후에 바로 .push() 를 해주고 싶었지만, 그렇게 사용할 수 없어서 위의 코드처럼 새로운 배열을 만들어서 바로바로 값을 갱신하는 방법을 선택했다.