백준: 1874 스택 수열

문제

1874번: 스택 수열

 

문제 풀이

 이 문제는 문제가 어려운게 아니라 처음에 문제를 접했을 때... 롸....? 이게 먼소리... 😣 라고 생각이 들었다. 문제를 찬찬히 읽으니 이건가? 하고 이해했다. 예제 입력 4, 3, 6, 8, 7 ,5, 2, 1이 주어지면 stack에 1 - n까지의 수를 어떻게 push, pop하여서 저러한 순열을 만들 수 있는가를 묻는 문제이다.

 

 순열의 처음이 4, 3이 되려면 stack에 1, 2, 3, 4를 순서대로 push하고 pop이 2번 되어야 한다. 그다음 6, 8이 출력 되려면 5, 6을 push하고 pop이 1번 되어야 한다. 즉, 다시 정리해보자면 다음과 같다.

 

• 입력이 주어지면 해당 값 까지의 1 부터 입력값까지 stack에 값을 추가한다.
  • 값이 중복되는 것을 막기 위해 카운트로 입력된 값을 확인한다.
• stack의 마지막으로 추가된 값이 입력값과 같으면 pop을 한다.
  • 아니라면 순열을 이용해 push pop하여 만들 수 없는 구성이다.

 

코드

from sys import stdin


def solution(n):
    count = 1
    stack = []
    answer = []

    for _ in range(n):
        num = int(stdin.readline())

        while count <= num:
            stack.append(count)
            answer.append('+')
            count += 1

        if stack[-1] == num:
            stack.pop()
            answer.append('-')
        else:
            return None
    return answer

if __name__ == "__main__":
    n = int(stdin.readline())
    ret = solution(n)
    if ret is None:
        print("NO")
    else:
        print('\n'.join(num for num in ret))