오큰수는 선택중인 숫자 X보다 오른쪽에 있으면서 X보다 큰 수 중 가장 왼쪽에 있는 수를 의미한다.
그런 수가 존재하지 않을 때는 -1을 출력한다.
-1을 출력하게 되는 경우는 두 가지다.
1) 맨 오른쪽의 숫자(마지막 번째 숫자)일 때
2) 오른쪽에 있는 숫자중에 X보다 큰 숫자가 없을 때
말을 따지고보면 1이 2에 포함되는 것처럼 보일 수 있다.
하지만 i와 i+1을 비교한다는 점에서 i+1번째가 존재하지 않는다면 런타임 에러를 야기할 수도 있다.
따라서 경우를 두 가지로 나눈 것이다.
문제 자체를 이해하는 것에는 어려움이 없지만, 막상 구현할 시에는 손가락이 멈추게 된다.
물론 이건 이 문제뿐만이 아니라 다른 문제에서도 그렇지만.
고민 끝에 복습 겸 재귀함수를 이용하여 구현해보았다.
재귀함수 'NGE'를 만들어주고, 그 안에서 -1을 출력하게 되는 경우를 조건문으로 써 주었다.
-1이 출력되는 조건은 오큰수를 탐색하다가 마지막까지 도달했음에도 오큰수가 없을 때이다.
지금 코드를 보면서 생각해보니 n-1번째 방의 숫자가 오큰수인 경우를 빼먹은 것같다.
시간초과로 발견하지 못했던 사실이다. 맨 앞에 조건문을 하나 더 추가해주는 것이 맞다.
그 외의 조건으로 오큰수를 발견했을 경우, 그리고 그다음 수를 탐색하기위해 재귀함수 호출이 일어난다.
그 함수를 반복문 내에서 호출한다. 반복문에서 이미 O(N)의 시간을 써버린데다,
재귀함수에 조건문까지 포함되었으니 당연하게도(?) 시간초과가 일어났다.
문제의 의도에 맞게 stack을 이용했다.
stack은 FIFO, FILO가 모두 자유자재로 가능한 deque 함수를 사용한다.
deque 라이브러리를 불러오는 방법은? from collections import deque.
함수를 따로 만들지 않고 바로 main으로 직행했다.
ans 자체를 -1이라는 값을 넣은 배열로 시작했다. 따로 또 append 할 필요가 없어서 좋다.
(구글링하면서 참고했다.)
stack은 2차원 배열로, stack의 첫번째 값은 오큰수를, 두번째 값은 index를 받는다.
n번만큼 반복하는 for 문 내에서 stack이 비어있지 않고,
해당 X가 stack의 마지막값보다 크면 계속 돌아가는 while문을 넣어준다.
맨 처음에는 while문 없이 stack.pop()을 하면 a[0],0(index) 값이 할당된다. ans에는 무엇도 할당되지 않는다.
1번째부터는 X 값이 stack[-1]의 숫자와 비교해서 X가 더 큰 경우 while문에서 다음 숫자를 탐색한다.
앞서 맨 처음 stack문에 할당된 값보다 크면 while문을 빠져나오고 stack 내의 값이 모두 사라지고 새롭게 갱신된다.
그리고 다시 for문 내에서 돈다.
만약 stack문에 할당된 값보다 작다면 while문을 돌지 않고 stack이 점점 쌓인다.
이때 stack은 업보와 같다. 미뤄뒀다가 다음, 다음, 다음... 하다가 결국 끝이 다가오면 ans 값에 다 할당해줘야한다.
while문 내에서 ans[idx]=a[i]가 이루어지기 때문이다.
만약 중간부터 끝까지 모두를 통틀어 더이상 큰 수가 없어 오큰수를 찾지 못했다면 그냥 업보빔(-1)을 맞는다.
그런 구조로 이루어진 반복문이다.
내가 손수 다 짠게 아니라 stack 문을 참고한 것이기 때문에 분석이 필요했다.
풀고나니 골드 4짜리 문제였다. 괜히 뿌듯하다.. 골드짜리 문제에 닿아보기도 전에 실버에서 많이 막혀서 ㅠㅠ
bfs, dfs문제도 연습해서 길들여져야겠다.
'공부 > 백준' 카테고리의 다른 글
| [백준] 2417번 (0) | 2022.06.15 |
|---|---|
| [백준] 17478번 (0) | 2022.06.15 |
| [백준] 2460번 (0) | 2022.06.15 |
| [백준] 25191번 (0) | 2022.06.15 |
| [백준] 1463번 (0) | 2022.06.15 |
