뒤에 있는 큰 수 찾기

문제설명

 

정수로 이루어진 배열 numbers가 있다. 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 한다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution함수를 완성하라. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담는다.

 

제한사항

 

4<= numbers의 길이 <= 1,000,000

 

1<= numbers[i] <= 1,000,000

 

입출력 예

 

numbers                                                          result

[2,3,3,5]                                                           [3,5,5,-1]

[9,1,5,3,6,2]                                                     [-1,5,6,6,-1,-1]

 

 

 

 

이 문제에서 numbers의 길이는 1,000,000이므로 시간복잡도가 0(N^2)가 되는 이중for문을 사용하면 시간초과가 걸린다.

그러므로 스택을 활용하여 문제를 해결하였다.

 

스택에는 Top이란 개념이 있기 때문에 좀 더 쉽게 특정 값에 접근할 수 있기 때문이다.

 

 

먼저 스택의 자료형과 MAX_SIZE를 정해준다.

 

 

그 다음 스택이 다 차있는지, 비어있는지 확인을 위한 Full,Empty함수를 선언한다.

 

 

스택에 값을 넣고, 빼는 Push와 Pop함수를 선언하면 스택 준비는 끝났다.

 

 

먼저 답을 나타내는 answer배열의 모든 값을 -1로 해준다. 그 이유는 answer배열의 마지막 값은 무조건 -1이고 ( 배열의 마지막 수 뒤에는 수가없기 때문에) , 뒤에 큰 수가 있을 때만 answer배열의 값을 바꿔주면 되기 때문이다. (뒤에 큰 수가 없는 경우에는 default값이 -1이기 때문에)

 

for문을 통해 numbers의 배열을 처음부터 끝까지 순회하면서, 현재 숫자보다 작은 숫자들의 인덱스를 스택에 저장한다. 그리고 현재 숫자보다 작은 숫자가 발견되면, 해당 숫자의 인덱스를 스택에서 꺼내여 answer배열에 현재 숫자를 기록한다.

 

이 코드는 각 요소를 스택에 한 번 넣고 한 번 빼므로, 전체 시간 복잡도가 O(N)이 된다.