오큰수 구하기(백준 17298번, 시간 제한: 1초)
문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
예시 입력
4
3 5 2 7
예시 출력
5 7 7 -1
예시 코드
import sys input=sys.stdin.readline n=int(input()) arr=list(map(int,input().split())) ans=[-1]*n stack=[] for i in range(n): while stack and arr[stack[-1]]<arr[i] : ans[stack.pop()]=arr[i] stack.append(i) #index를 stack에 넣어야 한다. print(*ans)
이 문제에서 n은 최대 백 만이다.
2중 반복문을 돌며 문제를 풀 수 없다는 뜻이다.
stack을 활용하여 문제를 풀어야 한다.
특징은 stack에 index를 저장하는 것이다.
stack의 top이 arr[i] 보다 작은지 확인하고 작다면 ans 배열에 해당 top index 부분에 arr[i]를 집어 넣는다.
그리고 stack에 index i 를 append 한다.
만약 arr[stack[-1]]<arr[i] 이게 없다면
ans[stack[-1]] 은 -1 이 나와야 하니
처음부터 -1로 ans 배열을 초기화 시키는 것이 시간복잡도를 줄이는 데 도움이 될 것이다.
추가적으로
print(*ans) 를 하면 list 같은 iterable 객체를 개별 요소로 분리하여 출력한다. space bar를 두고 출력된다.
굳이 반복문을 돌릴 필요가 없다!!
print(ans[i],end=" ")를 사용하면 마지막에 % 기호가 붙는다..? => 왜지?
