정수로 이루어진 배열 numbers
가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers
가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.
numbers
의 길이 ≤ 1,000,000
numbers[i]
≤ 1,000,000numbers | result |
---|---|
[2, 3, 3, 5] | [3, 5, 5, -1] |
[9, 1, 5, 3, 6, 2] | [-1, 5, 6, 6, -1, -1] |
입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.
입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
- numbers를 하나씩 아래과정으로 확인
- 현 numbers뒤에 있는 값중 앞에서부터 확인해서 큰 것 찾기
-> 찾았다면 그 값을 answer에 푸쉬
function solution(numbers) {
var answer = [];
for(var i =0;i<numbers.length;i++){
var num = -1;
for(var k = i+1;k<numbers.length; k++){
if(numbers[i]<numbers[k]){
num = numbers[k];
break;
}
}
answer.push(num);
}
return answer;
}
역시 이렇게 쉽게 풀리가 없지... 시간초과가 발생했다.. 어떻게 하면 시간복잡도를 줄일 수 있을까?
우선 시간 복잡도를 줄여야 했기 때문에 이중 for문 대신에 for문 하나로 해결할 수 있어야 된다. 이에 맞는 설계를 진행했다.
- 우선 아직 값이 정해지지 않는 인덱스를 담아낼 stack생성
또한 값이 정해지지 않는 것을 고려해 요소가 모두 -1 인 값을 가진 배열 생성
- numbers를 한번씩 돌면서 아래과정 체크
- 만일 스택에 값이 있고, stack 맨 앞 값 < numbers[i] 라면 그 stack index는 numbers[i] 가 가장 가까운 값이라고 정함.
그래서 스택에 있는 인덱스를 pop해주면서 그 값에는 numbers[i]의 값을 할당- 마지막에는 i인덱스를 스택에 푸쉬
function solution(numbers) {
var answer = new Array(numbers.length).fill(-1);
var stack = [];
for(var i =0;i<numbers.length;i++){
while(stack&&numbers[stack.at(-1)]<numbers[i]){
answer[stack.pop()] = numbers[i];
}
stack.push(i);
}
return answer;
}
이 설계는 굉장히 어려웠다... 하루동안 고민해도 도저히 생각이 안나서 프로그래머스에 질문하기란에 가서 스택
이라는 힌트를 얻어내고 풀었다... 이런 생각은 어떻게 하는건지... 너무 머리가 아팠다 ㅠㅠ 더 경험을 늘리는 수 밖에 없는 것 같다.