프로그래머스 39일차 - 뒤에 있는 큰 수 찾기

문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항
4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000

입출력 예 설명
입출력 예 #12의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.
입출력 예 #29는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

 

해설

처음에 이렇게 풀었는데, 

틀린 해답이었다.

이유는 리스트 내 num 중 다음 요소랑 비교해서 큰 숫자를 리턴하지 못했기 때문이다.

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

이렇게 결과를 리턴했었다.

 

그래서 위처럼 코드를 수정했다.

기준이 될 값을 지정해서 -1로 두고

2중 for문 안에서 num과 num2를 비교해야하므로 idx+1로 해서 같은 인덱스의 요소끼리 비교하지 않게 했다.

그래서 num2 >num이면 기준이 될 값을 치환했다.

 

그 치환 된 값을 result에 담았다.

근데, 시간 초과 문제가 떴다.

 

result에 요소수 만큼 -1를 미리 채워놓는다.

그리고 stack을 이용하자.

for문을 돌려 stack에 numbers의 요소를 넣는다.

 

[5,3,3,2]가 돌아가야하는데, 인덱스이니까 3부터 돌아갈것이다.

 

for문을 인덱스를 뒤부터 돌려서 뒤숫자랑 비교하게 만든다.

while문을 계속 돌리는데, stack이 없으면 비교가 안되므로 패쓰하고, 

stack이 있으면 마지막 요소와 numbers의 인덱스 요소를 비교해서 stack에서 마지막 요소를 빼낸다

 

stack이 있으면 스택의 마지막 요소를 -1대신 치환한다.