effort98   2년 전

i 인덱스의 오큰수를 찾지 못했어도 i+1 번째의 오큰수를 찾으면 자동으로 구해진다는데, 이해를 못하겠네요..

이건 제 추측인데

i = 2에서 stack에 2를 추가했잖아요. 그것때문에 i=2 의 while문이 다시 활성화 된건가요? (못알아먹겠다면 ㅈㅅ)

ppsrac   1년 전

이 코드의 알고리즘은 스택에 오큰수를 찾지 못한 수들을 저장하는 것입니다. 그리고 스택의 맨 위부터 배열의 수가 스택의 맨 위 수보다 클 때까지 계속 반복문을 돈 뒤 스택의 맨 위수를 제거하는 방식입니다. 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]이 되는 겁니다.

댓글을 작성하려면 로그인해야 합니다.