[백준][Python] 17298번 오큰수

17298번: 오큰수

 

코드

n = int(input())
a_list = list(map(int,input().split()))
a_list.reverse()

stack = [a_list[0]]
ans = [-1]

for i in range(1,n):
	flag = 0
	while stack:
		if stack[-1] > a_list[i]:
			ans.append(stack[-1])
			stack.append(a_list[i])
			flag = 1
			break
		else:
			stack.pop()
	if flag == 0:
		stack.append(a_list[i])
		ans.append(-1)
ans.reverse()
print(*ans)

 

설명

우선 주어진 a_list를 reverse를 이용하여 순서를 뒤집어준다.

가장 마지막 숫자 (뒤집어줬으니까 이제는 첫번째 숫자)는 항상 -1의 값을 갖기 때문에 ans에 미리 -1을 넣어두고 stack에 a_list[0]을 넣어놓는다.

stack의 가장 위에 있는 숫자가 가장 왼쪽에 있는 숫자이기 때문에 가장 위에 있는 숫자부터 while문을 이용하여 숫자가 존재하지 않을 때까지 비교를 해준다. 

 

만약 a_list[i]의 값이 stack[-1]의 값보다 크면 조건을 만족하지 않기 때문에 stack.pop()을 통해 값을 pop 시켜주고 해당 작업을 반복한다.

a_list[i] < stack[-1]의 조건을 만족한다면 ans에 stack[-1]을 추가하고 stack에 a_list[i]를 추가한 후 while문을 빠져나간다.

stack이 빌 때까지 조건을 만족하지 못했다면 ans에 -1을 추가해준다.

ans를 다시 뒤집어주고 출력을 한다.