https://www.acmicpc.net/problem/1874
문제
해설
처음에 풀 때 문제 이해가 잘 안되었다.. 결국 어떤 분의 설명을 블로그에서 읽고 겨우 이해했는데
만약 처음으로 4를 입력했다면
- 내가 첫 번째로 pop한 숫자가 4가 되어야 하고, 그러기 위해서는 1,2,3,4가 이미 스택안에 있어야 한다.
- 그래서 입력한 수를 만날 때 까지는 계속 push를 해서 1,2,3,4가 스택에 있도록 해야한다.
그래서 예제 입력을 하나씩 뜯어보자!
# 예제 입력
8 # 첫줄에 입력받을 수의 개수인 n을 입력받음
4 # 내가 처음 pop하고 싶은 수가 4임 그렇다면 1, 2, 3, 4까지 스택에 있어야함
# 그러므로 push 4번 해주어야 함 [ + + + + ]
# 그후 4를 pop [ - ]
3 # 3은 지금 스택에 1,2,3이 있으니 바로 pop가능 [ - ]
6 # 6은 스택에 1,2가 있으니까 5, 6 푸쉬하고 6을 pop해야 하므로 [+ + -]
8 # 8은 스택에 1,2,5 있으니까 7, 8 푸쉬하고 8을 pop해야하므로 [+ + -]
7 # 7은 바로 pop 가능 [ - ]
5 # 바로 pop 가능 [ - ]
2 # 바로 pop 가능 [ - ]
1 # 바로 pop 가능 [ - ]
코드
n = int(input())
count = 0
stack = []
result = []
msg = True
for i in range(n):
x = int(input())
while count < x: # 내가 입력한 수까지 푸쉬를 해주자
count += 1
stack.append(count)
result.append('+') # 푸쉬를 했다면 result 변수에 + 추가
if stack[-1] == x: # 스택의 맨 위의 값이 내가 pop하고자 하는 값과 같으면
stack.pop() # pop
result.append('-') # - 저장
else:
msg = False
exit(0)
if msg == False:
print("NO")
else:
print("\n".join(result))
'Algorithm > DataStructure' 카테고리의 다른 글
[Python] 백준 13417 카드 문자열 (0) | 2022.07.08 |
---|---|
[Python] 백준 10799 쇠막대기 (0) | 2022.07.08 |
[Python] 백준 3986 좋은 단어 (0) | 2022.07.08 |
[Python] 백준 2346 풍선 터뜨리기 (0) | 2022.07.08 |
[Python] 백준 1021 회전하는 큐 (0) | 2022.07.08 |
댓글