[Programmers] 뒤에 있는 큰 수 찾기 - JavaScript

Joosi_Cool·2023년 3월 22일

Programmers

목록 보기

49/98

문제설명

정수로 이루어진 배열 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]

입출력 예 설명

입출력 예 #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;
}