백준 17928번: 오큰수
오큰수
아이디어
수열의 크기가 1,000,000이다. O(NlogN)의 시간복잡도를 가진 알고리즘을 설계하면 풀 수 있을 것 같다. 그런데 이 문제는 O(N)의 시간복잡도로 풀 수 있다.
- 입력받은 수열을 역순으로 집어넣은 스택 A, 빈 스택 B를 만든다.
- 스택 B가 비어있으면 A에서 pop해서 스택 B에 push한다.
- 스택 B에 원소가 있다면, 스택 A의 최상단에 위치한 원소와 스택 B의 최상단에 위치한 원소를 비교한다.
- 스택 A의 최상단에 위치한 원소가 스택 B의 최상단에 위치한 원소보다 크다면, NGE(그 원소의 인덱스)를 스택 A의 최상단에 위치한 원소로 업데이트하고 pop한다.
- 스택 B의 최상단에 위치한 원소가 스택 A의 최상단에 위치한 원소보다 값이 커지거나, 스택 B에 원소가 없어질 때까지 반복한다.
- 스택 A에서 pop해서 스택 B에 push한다.
코드
import sys
input = sys.stdin.readline
N = int(input())
st = list(map(int, input().split()))
targets = []
ans = [-1] * N
st.reverse()
idx = 0
targets.append((idx, st.pop()))
while st:
t = st.pop()
idx += 1
while targets and targets[-1][1] < t:
a, b = targets.pop()
ans[a] = t
targets.append((idx, t))
for i in ans:
print(i, end=' ')
여담
문제풀기보다 그림그려서 설명하는게 어려움
Author And Source
이 문제에 관하여(백준 17928번: 오큰수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-17928번-오큰수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)