[백준] 스택 수열_1874번

스택 수열_1874번

코드

import sys
n = int(sys.stdin.readline())
nums = [i for i in range(1, n+1)]  # sorted array(1 ~ n)
seq = []  # input numbers
list = []

for _ in range(n):
    seq.append(int(sys.stdin.readline()))

answer = []
pointer = 0  # index pointer

while nums:
    if not list:  # empty
        answer.append('+')
        list.append(seq.pop(0))
    if nums[pointer] == list[0]:
        answer.append('-')
        nums.pop(pointer)
        list.pop(0)
        pointer -= 1
        pointer = max(0, pointer)
    elif nums[pointer] < list[0]:
        answer.append('+')
        list.append(seq.pop(0))
        pointer += 1
    else:
        answer = ["NO"]
        break

for a in answer:
    print(a)

풀이노트

문제 이해

• 1 2 3 4 5 6 7 8 오름차순 배열을 push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop 하면 4 3 6 8 7 5 2 1 수열을 만들 수 있음
• 1 2 5 3 4 수열은 1 2 3 4 5 로 만들 수 없으므로 "NO" 를 출력

문제 설명

• nums = [i for i in range(1, n+1)] # sorted array(1 ~ n) : 첫번째 input을 통해 1부터 n까지 오름차순 배열을 생성함
• if not list: # empty : seq 는 사용자로부터 받은 수열의 형태이고, nums 와 비교하기 위해서는 새로운 배열인 list 가 필요함. 시작할 때 숫자가 들어간 상태에서 시작하는 것이 아니라 + 하고 시작해야 함.
• pointer : nums 의 index 위치를 표시함
• seq.pop(0) 한 list 배열과 nums 배열을 pointer 로 비교하면서 answer 에 '+' 또는 '-' 를 삽입함
• if elif else
  • if nums[pointer] == list[0]: : 일치하는 경우 숫자를 pop 함
  • elif nums[pointer] < list[0]: : 한 칸 움직임
  • else: : 수열 생성 불가

예외 처리

• 예외 : 1 4 3 2 5 -> +-+++---+-
• pointer = max(0, pointer) : pointer 는 nums 의 index 를 표시하는 변수이므로, -1 이하 값을 가질 수 없음

소요시간 : 6시간