[백준 알고리즘] 17298번: 오큰수 (Python)

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

소스코드

 

 

풀이

★ 오큰수는 해당 수보다 큰 수 중 가장 처음으로 나오는 수입니다. 이번 문제는 일반적인 스택문제는 입력받는 리스트의 요소들을 스택에 넣고, 빼면서 풀이를 진행하지만 오큰수 문제는 입력 값의 '인덱스'를 사용하여 풀어야 하는 문제였습니다 ! 

 

★ 정답을 출력하기 위한 배열 ans는 -1로 초기화합니다. 그 이유는 해당 수의 오큰수가 없을 경우 -1이 출력되어야 하기 때문입니다. 

 

★ 인덱스를 사용하기 위해 for문을 n만큼 돌아줍니다. 이 때 stack이 비어있지 않고, 스택의 가장 윗부분의 값이 해당 값보다 작으면, stack의 최상단에 있는 값이 pop되면서, 그 수를 가지고 있는 ans의 인덱스에 해당 값이 들어가게 됩니다. 

EX) 

b = [3,5,2,7]

ans = [-1,-1,-1,-1]

stack = []

 

1. i = 0, stack이 비어있기 때문에 0이 stack에 들어갑니다.

 

2. i = 1, stack = [0], 스택의 최상단에는 0이 들어있고 b[0]은 3입니다. 3은 b[1]인 5보다 작기 때문에, 5가 3의 오큰수가 됩니다. 그렇기에 ans[0]에는 b[1]인 5가 들어가게 되고 ans = [5,-1,-1,-1]로 바뀝니다. 

 

★ 위와 같은 과정을 반복해준 뒤, ans를 출력합니다. 출력 과정에서 리스트 앞에 *를 붙여주면 리스트의 요소들이 공백을 기준으로 출력됩니다 !