190220 백준 알고리즘 문제풀기*
20 Feb 2019
|
baekjoon
[1874] 스택 수열*
문제
Input |
Stack |
출력 |
수열 |
4 |
4 |
+ |
|
|
3 |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
Input |
Stack |
출력 |
수열 |
|
|
- |
4 |
|
~~4~~ |
+ |
|
|
3 |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
Input |
Stack |
출력 |
수열 |
3 |
|
- |
4 |
|
~~4~~ |
+ |
|
|
3 |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
Input |
Stack |
출력 |
수열 |
|
|
- |
3 |
|
|
- |
4 |
|
~~4~~ |
+ |
|
|
~~3~~ |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
Input |
Stack |
출력 |
수열 |
6 |
6 |
+ |
|
|
5 |
+ |
|
|
|
- |
3 |
|
|
- |
4 |
|
~~4~~ |
+ |
|
|
~~3~~ |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
Input |
Stack |
출력 |
수열 |
|
|
- |
6 |
|
~~6~~ |
+ |
|
|
5 |
+ |
|
|
|
- |
3 |
|
|
- |
4 |
|
~~4~~ |
+ |
|
|
~~3~~ |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
Input |
Stack |
출력 |
수열 |
8 |
8 |
+ |
|
|
7 |
+ |
|
|
|
- |
6 |
|
~~6~~ |
+ |
|
|
5 |
+ |
|
|
|
- |
3 |
|
|
- |
4 |
|
~~4~~ |
+ |
|
|
~~3~~ |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
… (Stack 내부의 숫자가 위에서 아래 순서대로 지워진다.)
Input |
Stack |
출력 |
수열 |
7 |
|
- |
7 |
8 |
|
- |
8 |
|
~~8~~ |
+ |
|
|
~~7~~ |
+ |
|
|
|
- |
6 |
|
~~6~~ |
+ |
|
|
5 |
+ |
|
|
|
- |
3 |
|
|
- |
4 |
|
~~4~~ |
+ |
|
|
~~3~~ |
+ |
|
|
2 |
+ |
|
|
1 |
+ |
|
…
Input |
Stack |
출력 |
수열 |
1 |
|
- |
1 |
2 |
|
- |
2 |
5 |
|
- |
5 |
|
|
- |
7 |
|
|
- |
8 |
|
~~8~~ |
+ |
|
|
~~7~~ |
+ |
|
|
|
- |
6 |
|
~~6~~ |
+ |
|
|
~~5~~ |
+ |
|
|
|
- |
3 |
|
|
- |
4 |
|
~~4~~ |
+ |
|
|
~~3~~ |
+ |
|
|
~~2~~ |
+ |
|
|
~~1~~ |
+ |
|
- 뽑아내야 할 값이 현재 스택에 없어서 저장 후 뽑아내야 하는 값이라면
push
를 통해 해당 수를 만들고 바로 pop
을 1번 수행해 그 수를 뽑아낸다.
- 즉, 만일 뽑아내야 할 값이 스택에 현재 있는 값이라면
pop
을 수행해야 하므로 stack에 해당 값의 유무에 상관없이 무조건 1회의 pop
이 수행되어야 한다.
- 위의 예시에서, 8 4 3 6 8 7 ~~5~~ 2 1 로 5를 제외하고 뽑아내야 하는 경우는 출력 불가능하다(Stack은 LIFO)
- 즉,
pop
연산을 통해 최상위 값만 뽑아낼 수 있는 경우를 제외하곤 모두 “NO”를 출력해야 한다.
정답
class Stack:
def __init__(self):
self.len = 0
self.list = []
def push(self, num):
self.list.append(num)
self.len += 1
def pop(self):
if self.size() == 0:
return -1
pop_result = self.list[self.len-1]
del self.list[self.len-1]
self.len -= 1
return pop_result
def size(self):
return self.len
def empty(self):
return 1 if self.len == 0 else 0
def top(self):
return self.list[-1] if self.size() != 0 else -1
num = int(input()) # 몇 개의 숫자를 입력 받을지
stack = Stack() # 문제풀이를 위한 Stack 객체 선언
inputs = [] # 입력 저장용 list
outputs = [] # 출력 저장용 list
index = 0
# 입력을 받아 inputs 리스트 저장
for j in range(num):
inputs.append(int(input()))
# 각 loop의 시작점마다 push
for j in range(1, num+1):
stack.push(j)
outputs.append('+')
# index가 전체 숫자 개수보다 크고 스택의 맨 위 숫자가 현재번째 숫자와
# 같지 않다면 수열을 만들 수 없는 상태가 됨
# 그러한 경우 while문 안에서 pop을 수행하지 못해 스택에 숫자가 남아있게 됨
while index < num and stack.top() == inputs[index]:
stack.pop()
outputs.append('-')
index += 1
# 위의 while문에 따라 스택에 숫자가 남아있게 되면 수열을 만들지 못한것이므로 NO를 출력
if not stack.empty():
print('NO')
else:
for j in outputs:
print(j)