[Algorithm] 백준 6105 - Look Up (Node / C#)

문제

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

 

풀이

1. Node.js(fs)

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

const N = parseInt(input[0]);
const heights = input.slice(1).map(Number);

function findLookUp(heights) {
    const stack = [];
    const result = new Array(N).fill(0);

    for (let i = N - 1; i >= 0; i--) {
        while (stack.length > 0 && heights[stack[stack.length - 1]] <= heights[i]) {
            stack.pop();
        }
        if (stack.length > 0) {
            result[i] = stack[stack.length - 1] + 1;
        }
        stack.push(i);
    }

    return result;
}

const output = findLookUp(heights).join('\n');
console.log(output);

 

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. 알고리즘 (findLookUp 함수):
   • 소들의 높이 배열을 오른쪽에서 왼쪽으로 순회합니다.
   • 각 소에 대해:
     1. 스택의 top에 있는 소의 높이가 현재 소의 높이보다 작거나 같으면 pop합니다.
     2. 스택이 비어있지 않다면, 스택의 top에 있는 소의 인덱스 + 1을 결과 배열에 저장합니다.
     3. 현재 소의 인덱스를 스택에 push합니다.
3. 결과 출력:
   • 각 소에 대해 '올려다보는' 첫 번째 소의 인덱스를 출력합니다. 없으면 0을 출력합니다.
4. 시간 복잡도:
   • O(N), 여기서 N은 소의 수입니다.
   • 각 소는 한 번씩만 스택에 push되고 최대 한 번 pop됩니다.
5. 공간 복잡도:
   • O(N), 결과 배열과 스택에 각각 최대 N개의 요소가 들어갈 수 있습니다.