[Algorithm] 백준 2841 - 외계인의 기타 연주 (Node / C#)

문제

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

풀이

1. Node.js(fs)

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

// 첫 번째 줄에서 음의 수 N과 프렛의 수 P를 파싱
const [N, P] = input[0].split(' ').map(Number);

// 각 줄별로 프렛을 누르고 있는 상태를 저장할 배열
const strings = Array.from({ length: 7 }, () => []);

let fingerMoves = 0;

// 각 음을 처리
for (let i = 1; i <= N; i++) {
    const [string, fret] = input[i].split(' ').map(Number);
    
    // 현재 줄에서 더 높은 프렛을 누르고 있는 손가락을 뗌
    while (strings[string].length > 0 && strings[string][strings[string].length - 1] > fret) {
        strings[string].pop();
        fingerMoves++;
    }
    
    // 이미 같은 프렛을 누르고 있지 않다면 새로운 프렛을 누름
    if (strings[string].length === 0 || strings[string][strings[string].length - 1] < fret) {
        strings[string].push(fret);
        fingerMoves++;
    }
}

console.log(fingerMoves);

 

2. Node.js(readLine)

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let N, P;
let currentLine = 0;
const strings = Array.from({ length: 7 }, () => []);
let fingerMoves = 0;

rl.on('line', (line) => {
    if (currentLine === 0) {
        [N, P] = line.split(' ').map(Number);
    } else {
        const [string, fret] = line.split(' ').map(Number);
        
        // 현재 줄에서 더 높은 프렛을 누르고 있는 손가락을 뗌
        while (strings[string].length > 0 && strings[string][strings[string].length - 1] > fret) {
            strings[string].pop();
            fingerMoves++;
        }
        
        // 이미 같은 프렛을 누르고 있지 않다면 새로운 프렛을 누름
        if (strings[string].length === 0 || strings[string][strings[string].length - 1] < fret) {
            strings[string].push(fret);
            fingerMoves++;
        }
    }
    
    currentLine++;
    if (currentLine > N) {
        console.log(fingerMoves);
        rl.close();
    }
});

3. C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int P = int.Parse(input[1]);

        List<int>[] strings = new List<int>[7];
        for (int i = 0; i < 7; i++)
        {
            strings[i] = new List<int>();
        }

        int fingerMoves = 0;

        for (int i = 0; i < N; i++)
        {
            input = Console.ReadLine().Split();
            int stringNum = int.Parse(input[0]);  // 'string'을 'stringNum'으로 변경
            int fret = int.Parse(input[1]);

            // 현재 줄에서 더 높은 프렛을 누르고 있는 손가락을 뗌
            while (strings[stringNum].Count > 0 && strings[stringNum][strings[stringNum].Count - 1] > fret)
            {
                strings[stringNum].RemoveAt(strings[stringNum].Count - 1);
                fingerMoves++;
            }

            // 이미 같은 프렛을 누르고 있지 않다면 새로운 프렛을 누름
            if (strings[stringNum].Count == 0 || strings[stringNum][strings[stringNum].Count - 1] < fret)
            {
                strings[stringNum].Add(fret);
                fingerMoves++;
            }
        }

        Console.WriteLine(fingerMoves);
    }
}

 

 

설명

1. 입력 처리:
   • 첫 번째 줄에서 음의 수 N과 프렛의 수 P를 읽습니다.
   • 그 다음 N개의 줄에서 각 음의 줄 번호와 프렛 번호를 읽습니다.
2. 데이터 구조:
   • 각 기타 줄별로 현재 누르고 있는 프렛을 저장하기 위해 배열(또는 리스트)의 배열을 사용합니다.
   • 각 줄의 프렛은 스택처럼 동작하며, 항상 가장 높은 프렛만 소리가 납니다.
3. 알고리즘:
   • 각 음을 처리할 때마다:
     1. 현재 줄에서 더 높은 프렛을 누르고 있는 손가락을 모두 뗍니다.
     2. 필요한 경우 새로운 프렛을 누릅니다.
   • 손가락을 떼거나 새로 누를 때마다 손가락 움직임 횟수를 증가시킵니다.
4. 결과 출력:
   • 모든 음을 처리한 후 총 손가락 움직임 횟수를 출력합니다.