[BOJ/Python] 백준 17298 오큰수
문제
https://www.acmicpc.net/problem/17298
풀이
풀이1
- 255784 KB, 596 ms(Pypy), 155584 KB, 1092 ms (Python)
import sys
input = sys.stdin.readline
N = int(input().rstrip()) # 수열 A 의 길이 N
A = list(map(int, input().rstrip().split())) # 수열 A
stack = []
NGE = [-1] * N
for i in range(N - 1, -1, -1) :
while stack and stack[-1] <= A[-1] :
stack.pop()
if stack : NGE[i] = stack[-1]
stack.append(A.pop())
print(*NGE)
풀이1 설명
스택문제는 누가봐도 짝 맞추기인 문제가 아니면 풀이 떠올리기가 아직 좀 어렵다..
- 1. 문제의 조건
-
시간 제한 1초인데 N의 범위가 1,000,000 → O(N^2)로 풀면 안된다 (for문 두번 돌리면 안된다)
→ 스택, 큐 …
2. 정답을 어떤 방향으로 찾을 것인가?
1) NGE[-1]은 무조건 -1(가장 오른쪽이므로)
2) 오른쪽에 있는 수를 기준으로 찾으므로, 찾는 범위를 점점 늘려갈 수 있도록 (dp처럼)
(그리고 왼쪽부터 구하면 최악의 경우에는 처음부터 전체를 다 확인해봐야할 수 있다)
→ 오른쪽 부터 찾자 !
3. 예제 풀어보기
| 수열 A | stack | 정답 | 설명 |
|---|---|---|---|
| 3 5 2 7 | -1 -1 -1 -1 | 초기 상태 | |
| 3 5 2 | 7 | -1 -1 -1 -1 | A[-1]인 7의 NGE를 구함 - len(stack) == 0 이므로 NGE는 -1 - 확인한 A[-1]을 pop하고 stack에 append (NGE 후보) |
| 3 5 | 7 2 | -1 -1 7 -1 | A[-1]인 2의 NGE를 구함 - stack[-1]인 7보다 2가 작음. 따라서 NGE는 7 - 확인한 A[-1]을 pop하고 stack에 append (NGE 후보) |
| 3 | 7 ~2~ 5 | -1 7 7 -1 | A[-1]인 5의 NGE를 구함 - stack[-1]인 2보다 5가 작지 않음 - 2는 더 이상 다른 수의 NGE가 될 수 없으므로 pop한다. (stack[-1]이 A[-1]보다 클 때까지 stack을 pop) (왜냐하면 2가 NGE려면 2보다 작은 수가 나와야하는데(ex. 1), 이 수의 NGE는 2보다 더 왼쪽에 있는 수인 5가 될 것임) - stack[-1]인 7보다 5가 작음. 따라서 NGE는 5 - 확인한 A[-1]를 pop하고 stack에 append (NGE 후보) |
| 7 5 3 | 5 7 7 -1 | A[-1]인 3의 NGE를 구함 - stack[-1]인 5보다 3가 작음. 따라서 NGE는 5 - 확인한 A[-1]을 pop하고 stack에 append (NGE 후보) |
예제에서 확인한 규칙에 따라 풀이를 작성
풀이2
- 263552 KB, 616 ms(Pypy)
- 참고 풀이
import sys
input = sys.stdin.readline
N = int(input().rstrip()) # 수열 A 의 길이 N
A = list(map(int, input().rstrip().split())) # 수열 A
stack = [0]
NGE = [-1] * N
for i in range(1, N) :
while stack and A[stack[-1]] < A[i] :
NGE[stack.pop()] = A[i]
stack.append(i)
print(*NGE)
풀이2 설명
- stack에는 NGE를 구해야하는 요소의 인덱스를 담음
- 무조건 연속한 두 요소만을 비교 (index i, i +1을 비교하여 i의 NGE 구함)
- A[i] < A[i+1]이면 stack을 pop (stack에 i 있음). A[i]의 오큰수는 A[i+1]
- 그렇지 않은 경우, stack은 유지 (i가 stack에 있는 상태). 이후에 찾은 A[i+1]의 오큰수는 A[i]의 오큰수가 될 수도 있음
이와 같은 규칙으로 코드 작성
Leave a comment