[백준 1874번] 스택 수열 - 파이썬

 

① 문제 링크

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

1874번: 스택 수열

---

② 알고리즘 분류

자료 구조, 스택

---

③ ★문제풀이 Point★

1. 스택(stack)을 제대로 알고 있는지 여부 

2. 스택에 push 하는 순서는 반드시 오름차순인 점

---

④ 풀이

이 문제는 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지 프로그램을 작성하는 문제다.

스택이란??

스택(stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

스택: LIFO(Last in First Out) 특성

 

문제의 예제를 참고해 문제를 이해해보자.

다음과 같이 수열이 있다고 하자.

수열(s): [4, 3, 6, 8, 7, 5, 2, 1]

먼저 수열의 맨 처음 숫자인 4를 만들려면 다음과 같이 실행해야 한다.

stack = [1] <= push(1 넣기) +

stack = [1, 2] <= push(2 넣기) +

stack = [1, 2, 3] <= push(3 넣기) + 

stack = [1, 2, 3, 4] <= push(4 넣기) + 

stack에 4가 있기 때문에 stack에서 4를 뺀다.

stack = [1, 2, 3] <= pop(4 빼기) -

 

이제 그 다음 숫자인 3을 만들어야 한다.

stack의 맨 마지막 숫자가 3이므로 스택의 LIFO 구조로 인해 stack에서 3을 뺀다.

stack = [1, 2] <= pop(3 빼기) -

 

그 다음으로 숫자 6을 만들자.

stack = [1, 2, 5] <= push(5 넣기) +

stack = [1, 2, 5, 6] <= push(6 넣기) + 

이제 6이 stack(스택) 안에 있으므로 빼준다.

stack = [1, 2, 5] <= pop(6 빼기) -

 

이러한 방법으로 push와 pop을 이용하여 수열(s): [4, 3, 6, 8, 7, 5, 2, 1]을 만드는 것이다.

스택에 push하는 순서가 반드시 오름차순이기에 시작 숫자(now)를 지정하여 코드를 구현하면 해결할 수 있다.

 

⑤ 코드

다음 코드는 Python으로 작성하였습니다.

# 1874번 스택 수열
n = int(input())
stack, ans, find = [], [], True
# 숫자 1부터 시작
now = 1
for _ in range(n):
    num = int(input())
    # 스택 쌓기 Push
    while now <= num:
        stack.append(now)
        ans.append('+')
        now += 1
    # 스택 꺼내기 Pop
    if stack[-1] == num:
        stack.pop()
        ans.append('-')
    # 불가능한 경우
    else:
        find = False

# 정답 출력
if not find: # 불가능하다면
    print('NO')
else:
    for i in ans: # 가능하다면
        print(i)

 

1874 파이썬 채점 결과

---

1874번 스택 수열