[백준] 1874. 스택 수열 풀이 / Python, JavaScript

1874번: 스택 수열

 

작성 코드 (.py)

import sys
input = sys.stdin.readline

n = int(input())
result, s, a = [], [], 1
for _ in range(n):
    now = int(input())
    if s and s[-1] == now:
        s.pop()
        result.append("-")
    else:
        for i in range(a, now + 1):
            s.append(i)
            result.append("+")
        s.pop()
        result.append("-")
        a = now + 1
if not s:
    for i in result:
        print(i)
else:
    print("NO")

작성 코드 (.js)

function solution(arr) {
  let [result, s, a] = [[], [], 1];
  arr.forEach((v) => {
    if (s.length && s[s.length - 1] == v) {
      s.pop();
      result.push("-");
    } else {
      for (let i = a; i <= v; i += 1) {
        s.push(i);
        result.push("+");
      }
      s.pop();
      result.push("-");
      a = v + 1;
    }
  });
  if (!s.length) return result;
  else return "NO";
}

 

구현 로직

문제에서 들어오는 입력의 수열을 pop연산을 통해서 구현해야합니다. 다음 두가지 과정만 구현하면 풀어낼 수 있습니다.

입력값을 하나씩 받고 아래 두 케이스 중 하나를 수행합니다.

1. 현재 스택이 비어있지 않고 스택의 최상단(top)값이 현재 입력값과 같다면 pop을 수행합니다.

2. 1부터 입력값이 나올때까지 스택에 값을 넣습니다. 넣고난 후부터 다음 push 수행이 일어날 때는 스택에 마지막으로 넣었던 값 + 1부터 넣습니다.

 

이렇게 하고난 후 스택이 비어있다면 수열 완성이 가능한 것이며 스택이 남아있다면 수열을 만들 수 없는 경우입니다.