[Python] 백준 1874번 문제 풀이 - 스택 수열

문제

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

아이디어

이 문제는 1부터 N까지 자연수를 오름차순으로 원하는대로 push, pop해서 입력의 두번째줄부터 마지막까지의 수열을 만들 수 있는지 확인하고 가능하다면 push하는 연산은 + 출력, pop하는 연산은 -를 출력하고, 가능하지 않다면 NO를 출력하는 문제입니다.

 

입력1부터 따라해보며 진행했습니다.

입력1의 첫번째 수는 4입니다. 4번 push(1,2,3,4) 후 1번 pop(4) 합니다.

두번째 수는 3입니다. 이미 스택의 맨 위에 3이 있으므로 1번 pop(3) 합니다.

세번째 수는 6입니다. 2번 push(5,6) 후 1번 pop(6)합니다.

네번째 수는 8입니다. 2번 push(7,8)후 pop(8)합니다.

다섯번째 수는 7입니다. 스택의 맨 위에 7이 있으므로 pop(7)합니다.

여섯번째 수는 5입니다. 스택의 맨 위에 5가 있으므로 pop(5)합니다.

일곱번째 수는 2입니다. 스택의 맨 위에 2가 있으므로 pop(2)합니다.

여덟번째 수는 1입니다. 스택의 맨 위에 1이 있으므로 pop(1)합니다.

 

push할 때 +를 출력하고 pop할 때 -를 출력해주면 됩니다.

 

구현하는데 떠올려야할 아이디어는 숫자를 어디까지 넣었는지 변수에 저장하고 변수를 사용해 반복문 조건을 거는 것이였습니다.

 

구현방법

1. 구현하는 것은 arr 배열을 만들어 수열을 저장해둡니다.

2. 수열 요소 하나씩 뽑아내기 위해 수열 요소의 반복문을 돕니다.

3. 스택에  1, 2, ... , x-1, x 까지 넣어야 하기 때문에, cnt를 1로 초기화하고 반복문을 돌며 1씩 증가시켜 스택에 넣고 어디까지 넣었는지 기억하고 결과 배열에 출력을 위한 +를 삽입합니다.

4. 스택의 맨 위의 수와 현재 수가 같다면 pop을 하고, -를 결과 배열에 삽입하고, 다르다면 스택으로 수열을 완성할 수 없으므로 flag를 False로 만들고 반복문을 탈출합니다.

5. 이 모든 과정이 끝나고 수열을 만들 수 있다면 결과 배열에 있는 +, -를 출력하고, 불가능하다면 NO를 출력합니다.

소스코드

n = int(input())
arr = []
stack = []
cnt = 1
res = []
flag = True

for _ in range(n):
    arr.append(int(input()))

for x in arr:
    while cnt <= x:
        stack.append(cnt)
        cnt += 1
        res.append("+")

    if stack[-1] == x:
        stack.pop()
        res.append("-")
    else:
        flag = False
        break

if flag:
    for i in res:
        print(i)
else:
    print("NO")

 

느낀 점

코드를 짰는데, 이것을 보는 사람이 이해 할 수 있게 글을 쓰려니깐 막히는 부분이 많았습니다.

블로그를 쓰며 오랜 시간이 걸렸지만 한번 더 생각을 정리할 수 있는 계기가 되어 좋았습니다.