[Algorithm] 백준 5957 - Cleaning the Dishes (Node / C#)

문제

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

 

풀이

1. Node.js(fs)

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

const N = parseInt(input[0]);
let unwashed = Array.from({length: N}, (_, i) => N - i);
let washed = [];
let dried = [];

for (let i = 1; i < input.length; i++) {
    const [C, D] = input[i].split(' ').map(Number);
    if (C === 1) {  // Bessie washing
        for (let j = 0; j < D; j++) {
            if (unwashed.length > 0) {
                washed.push(unwashed.pop());
            }
        }
    } else {  // Canmuu drying
        for (let j = 0; j < D; j++) {
            if (washed.length > 0) {
                dried.push(washed.pop());
            }
        }
    }
}

console.log(dried.reverse().join('\n'));

 

2. Node.js(readLine)

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

let N;
let unwashed, washed, dried;
let lineCount = 0;

rl.on('line', (line) => {
    if (!N) {
        N = parseInt(line);
        unwashed = Array.from({length: N}, (_, i) => N - i);
        washed = [];
        dried = [];
    } else {
        const [C, D] = line.split(' ').map(Number);
        if (C === 1) {  // Bessie washing
            for (let j = 0; j < D; j++) {
                if (unwashed.length > 0) {
                    washed.push(unwashed.pop());
                }
            }
        } else {  // Canmuu drying
            for (let j = 0; j < D; j++) {
                if (washed.length > 0) {
                    dried.push(washed.pop());
                }
            }
        }
        lineCount++;
    }
});

rl.on('close', () => {
    // 남은 접시들 처리
    while (washed.length > 0) {
        dried.push(washed.pop());
    }
    console.log(dried.reverse().join('\n'));
});

3. C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        Stack<int> unwashed = new Stack<int>(Enumerable.Range(1, N).Reverse());
        Stack<int> washed = new Stack<int>();
        Stack<int> dried = new Stack<int>();

        string line;
        while ((line = Console.ReadLine()) != null && line != "")
        {
            string[] parts = line.Split(' ');
            int C = int.Parse(parts[0]);
            int D = int.Parse(parts[1]);

            if (C == 1)  // Bessie washing
            {
                for (int j = 0; j < D && unwashed.Count > 0; j++)
                {
                    washed.Push(unwashed.Pop());
                }
            }
            else  // Canmuu drying
            {
                for (int j = 0; j < D && washed.Count > 0; j++)
                {
                    dried.Push(washed.Pop());
                }
            }
        }

        // 남은 접시들 처리
        while (washed.Count > 0)
        {
            dried.Push(washed.Pop());
        }

        foreach (int dish in dried)
        {
            Console.WriteLine(dish);
        }
    }
}

 

 

설명

 

1. 데이터 구조:
   • 세 개의 스택을 사용합니다: unwashed, washed, dried
   • unwashed: 아직 세척되지 않은 접시들을 저장
   • washed: 세척되었지만 아직 건조되지 않은 접시들을 저장
   • dried: 세척과 건조가 완료된 접시들을 저장
2. 알고리즘:
   • 입력을 순회하며 다음과 같이 처리합니다:
     1. Bessie가 세척하는 경우 (C = 1):
        • unwashed에서 D개의 접시를 꺼내 washed로 옮깁니다.
     2. Canmuu가 건조하는 경우 (C = 2):
        • washed에서 D개의 접시를 꺼내 dried로 옮깁니다.
   • 모든 입력 처리가 끝난 후, washed에 남아있는 접시들을 dried로 옮깁니다.
3. 결과 출력:
   • dried 스택의 접시들을 위에서부터 순서대로 출력합니다.
4. 시간 복잡도:
   • 각 접시를 최대 두 번 (세척과 건조) 처리하므로 O(N)입니다. 여기서 N은 접시의 총 개수입니다.
5. 공간 복잡도:
   • 세 개의 스택을 사용하며, 각각 최대 N개의 접시를 저장할 수 있으므로 O(N)입니다.