이 코드의 알고리즘은 스택에 오큰수를 찾지 못한 수들을 저장하는 것입니다. 그리고 스택의 맨 위부터 배열의 수가 스택의 맨 위 수보다 클 때까지 계속 반복문을 돈 뒤 스택의 맨 위수를 제거하는 방식입니다. N=6, [3,5,2,4,1,7]을 예시로 들자면,
시행전:
stack: [0(3을 가리킵니다)], answer=[-1 -1 -1 -1 -1 -1]
1번째: 5가 3보다 크므로 stack에서 3제거,answer의 3자리에 5를 대입. 그 후 stack에 1추가(5의 인덱스)
stack: [1], answer=[5 -1 -1 -1 -1 -1]
2번째: 2가 5보다 작으므로 stack에 2추가(2의 인덱스)
stack: [1 2], answer=[5 -1 -1 -1 -1 -1]
3번째: stack의 맨 위(2)가 가리키는 숫자 2가 4보다 작으므로 stack에서 2를 pop한 후 answer[2]에 4대입
이 때 1이 가리키는 숫자 5가 4보다 크므로 1은 stack에서 pop하지 못함. 그 후 3을 stack에 추가
stack: [1 3], answer=[5 -1 4 -1 -1 -1]
4번째: stack의 맨 위(3)이 가리키는 숫자 4보다 1이 작으므로 stack에 4 추가
stack: [1 3 4], answer=[5 -1 4 -1 -1 -1]
5번째: stack의 맨 위(4)가 가리키는 숫자 1보다 7이 크므로 stack에서 4를 pop한 후 answer[4]=7대입 stack: [1 3], answer=[5 -1 4 -1 7 -1]
stack의 맨 위(3)이 가리키는 숫자 4보다 7이 크므로 stack에서 3을 pop한 후 answer[3]=7 대입 stack: [1], answer=[5 -1 4 7 7 -1]
stack의 맨 위(1)이 가리키는 숫자 5보다 7이 크므로 stack에서 1을 pop한 후 answer[1]=7 대입 stack: [], answer=[5 7 4 7 7 -1]
그리고 stack에 5를 push합니다. (맨 마지막에 stack에 5를 push하는 것은 사실 필요 없습니다.)
이를 다 거치면 답이 [5 7 4 7 7 -1]이 되는 겁니다.
effort98 2년 전
i 인덱스의 오큰수를 찾지 못했어도 i+1 번째의 오큰수를 찾으면 자동으로 구해진다는데, 이해를 못하겠네요..
이건 제 추측인데
i = 2에서 stack에 2를 추가했잖아요. 그것때문에 i=2 의 while문이 다시 활성화 된건가요? (못알아먹겠다면 ㅈㅅ)