[Algorithm] 백준 5966 - Cow Cotillion (Node / C#)

문제

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

 

풀이

1. Node.js(fs)

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

const N = parseInt(input[0]);

function isLegal(pattern) {
    const stack = [];
    for (let char of pattern) {
        if (char === '>') {
            stack.push(char);
        } else if (char === '<') {
            if (stack.length === 0 || stack[stack.length - 1] !== '>') {
                return false;
            }
            stack.pop();
        }
    }
    return stack.length === 0;
}

let output = '';
for (let i = 1; i <= N; i++) {
    const [K, pattern] = input[i].split(' ');
    output += (isLegal(pattern) ? 'legal' : 'illegal') + '\n';
}

console.log(output.trim());

 

2. Node.js(readLine)

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

let N;
let count = 0;
let output = '';

function isLegal(pattern) {
    const stack = [];
    for (let char of pattern) {
        if (char === '>') {
            stack.push(char);
        } else if (char === '<') {
            if (stack.length === 0 || stack[stack.length - 1] !== '>') {
                return false;
            }
            stack.pop();
        }
    }
    return stack.length === 0;
}

rl.on('line', (line) => {
    if (!N) {
        N = parseInt(line);
    } else {
        const [K, pattern] = line.split(' ');
        output += (isLegal(pattern) ? 'legal' : 'illegal') + '\n';
        count++;
        if (count === N) {
            console.log(output.trim());
            rl.close();
        }
    }
});

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. 데이터 구조:
   • 스택을 사용하여 소와 황소의 짝을 확인합니다.
2. 알고리즘 (isLegal 함수):
   • 패턴 문자열을 순회하며 다음과 같이 처리합니다:
     1. '>'를 만나면 스택에 푸시합니다.
     2. '<'를 만나면:
        • 스택이 비어있거나 스택의 top이 '>'가 아니면 불법(illegal)입니다.
        • 그렇지 않으면 스택에서 pop합니다.
   • 모든 문자를 처리한 후, 스택이 비어있으면 합법(legal), 그렇지 않으면 불법(illegal)입니다.
3. 결과 출력:
   • 각 패턴에 대해 'legal' 또는 'illegal'을 출력합니다.
4. 시간 복잡도:
   • 각 패턴에 대해 O(K)이며, K는 패턴의 길이입니다.
   • 전체 시간 복잡도는 O(N * K)입니다. 여기서 N은 패턴의 수입니다.
5. 공간 복잡도:
   • 각 패턴에 대해 O(K)의 공간이 필요합니다.