[Algorithm] 백준 1874 - 스택 수열 (Node / C#)

문제

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

풀이

1. Node.js(fs)

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

const n = parseInt(input[0]);
const sequence = input.slice(1).map(Number);

const stack = [];
let result = [];
let current = 1;

for (let i = 0; i < n; i++) {
  // 수열의 현재 숫자보다 작거나 같으면 push
  while (current <= sequence[i]) {
    stack.push(current++);
    result.push('+');
  }

  // 스택의 최상단이 수열의 현재 숫자와 같으면 pop
  if (stack[stack.length - 1] === sequence[i]) {
    stack.pop();
    result.push('-');
  } else {
    console.log('NO');
    return;
  }
}

console.log(result.join('\n'));

 

2. Node.js(readLine)

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

let input = [];
rl.on('line', (line) => {
  input.push(line);
}).on('close', () => {
  const n = parseInt(input[0]);
  const sequence = input.slice(1).map(Number);

  const stack = [];
  let result = [];
  let current = 1;

  for (let i = 0; i < n; i++) {
    // 수열의 현재 숫자보다 작거나 같으면 push
    while (current <= sequence[i]) {
      stack.push(current++);
      result.push('+');
    }

    // 스택의 최상단이 수열의 현재 숫자와 같으면 pop
    if (stack[stack.length - 1] === sequence[i]) {
      stack.pop();
      result.push('-');
    } else {
      console.log('NO');
      return;
    }
  }

  console.log(result.join('\n'));
});

3. C#

using System;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[] sequence = new int[n];

        for (int i = 0; i < n; i++)
        {
            sequence[i] = int.Parse(Console.ReadLine());
        }

        Stack<int> stack = new Stack<int>();
        StringBuilder result = new StringBuilder();
        int current = 1;

        for (int i = 0; i < n; i++)
        {
            // 수열의 현재 숫자보다 작거나 같으면 push
            while (current <= sequence[i])
            {
                stack.Push(current++);
                result.AppendLine("+");
            }

            // 스택의 최상단이 수열의 현재 숫자와 같으면 pop
            if (stack.Peek() == sequence[i])
            {
                stack.Pop();
                result.AppendLine("-");
            }
            else
            {
                Console.WriteLine("NO");
                return;
            }
        }

        Console.WriteLine(result.ToString());
    }
}

 

설명

1. 스택을 이용한 수열 생성:
   • 두 개의 스택을 사용하여 주어진 수열을 생성합니다.
   • 현재 스택에 넣을 수 있는 최대 수를 current 변수로 관리합니다.
   • 수열의 각 숫자를 처리하면서 필요한 연산을 기록합니다.
2. 주요 로직 설명:
   • current가 수열의 현재 숫자보다 작거나 같으면 스택에 current를 추가하고 current를 증가시킵니다.
   • 스택의 최상단이 수열의 현재 숫자와 같으면 스택에서 제거하고 - 연산을 기록합니다.
   • 스택의 최상단이 수열의 현재 숫자와 다르면 주어진 수열을 만들 수 없으므로 NO를 출력하고 종료합니다.
3. 최종 출력:
   • 연산 기록을 출력하여 주어진 수열을 만들기 위한 연산 순서를 보여줍니다.