[ Programmers ] lv2_뒤에 있는 큰 수 찾기(JS)

프로그래머스

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

 

풀이 및 코드

 

문제를 보고 dp로 풀어야겠다는 생각이 들었다.

 

문제의 요구 사항을 따르면, numbers 배열이 [2, 3, 3, 5] 이렇게 되어있을 때 numbers[i] 즉, 현재 요소가 2일 때 그 뒤에 있는 요소들을 하나씩 보면서 현재 요소 2보다 크다면 현재 요소를 그 뒤에 있는 큰 수로 바꿔나가야 한다.라는 것을 알 수 있다.

 

dp란 무엇이었나

• DP는 일반적으로 최적화 문제를 해결하기 위한 기법으로 사용된다.
        - 최적화 문제란, 여라가지 가능한 해 중에서 가장 좋은 해를 찾는 문제를 말한다.
• DP는 이전에 계산된 값을 저장해두었다가 다시 사용하는 기법이다.

 

dp를 이용해서 처음에 풀었던 코드는 아래와 같다.

function solution(numbers) {  
    // numbers 배열 요소 수에 맞게 dp배열 생성,0으로 초기화
    const dp = Array(numbers.length).fill(0);
    
    // getMaxValue 함수에 현재 요소, 현재 요소를 제외한 뒤에있는 수들을 보내서 max 값을 받아 
    // numbers 배열 현재 요소 위치에 맞게 dp요소에 max 값을 저장한다.
    for (let i = 0; i < numbers.length; i++) {
        dp[i] = getMaxValue(numbers[i], numbers.slice(i + 1));
    } 
    // 만들어진 dp 배열 리턴
    return dp;
}

function getMaxValue(num, arr) {
    let maxValue = -1; 
    // 들어온 현재 요소보다 arr 요소가 크면 maxValue 값을 arr요소로 바꿔주고 중단
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > num) {
            maxValue = arr[i];
            break;
        }
    }
    // max 값 리턴
    return maxValue;
}

이 코드로 채점할때 정확성에서 반 이상이 나가떨어졌다...

테스트 9번에서부터 시간초과가 나왔다..

도저히 이유를 모르겠어서 스터디원 형님께 여쭤봤는데 이건 dp로 푼게 아니라고 말씀하셨당;

dp의 핵심은 계산했던 값을 재활용하는 것인데 그걸 안하고 있다고 재활용을 어떻게 할 수 있을지를 고민해보라고 하셨다..

내가 dp에 대해서 아직 완전히 딥하게 이해를 못한 것 같다.

 

다시 한번 고민해본 결과, 

내가 쓴 코드에서는 재활용을 하고 있지 않다. 단순히 솔루션 함수에서 포문을 돌려 getMaxValue 함수에 값을 보내고 받은 다음, dp 배열의 요소들에 저장만 하고 있었다.

 

다시 작성한 코드

function solution(numbers) {
    // numbers 배열 요소 수에 맞게 dp 배열 생성, -1로 초기화
    const dp = Array(numbers.length).fill(-1);

    // 뒤에서부터 dp 값을 업데이트하면서 최대값 찾기
    for (let i = numbers.length - 2; i >= 0; i--) {
        if (numbers[i] < numbers[i + 1]) {
            dp[i] = numbers[i + 1];
        } else {
            let j = i + 1;
            while (dp[j] !== -1) {
                if (numbers[i] < dp[j]) {
                    dp[i] = dp[j];
                    break;
                }
                j++;
            }
        }
    }

    // 만들어진 dp 배열 리턴
    return dp;
}

 

풀이 - 핵심 로직 

for (let i = numbers.length - 2; i >= 0; i--) {
    if (numbers[i] < numbers[i + 1]) {
        dp[i] = numbers[i + 1];
    } else {
        let j = i + 1;
        while (dp[j] !== -1) {
            if (numbers[i] < dp[j]) {
                dp[i] = dp[j];
                break;
            }
            j++;
        }
    }
}

 

 

처음 조건문 : numbers 배열의 현재 수가 다음 수 보다 작으면,

dp배열의 현재 수를 dp배열의 현재 수를 numbers 현재 수의 다음 수로 저장한다.

포문의 i 는 numbers.length - 2 부터 시작해서 거꾸로 반복되기 때문에 
포문이 시작했을 때 i는 2부터 시작한다.
numbers[2] 는 3, numbers[3] 은 5 이기 때문에 numbers[i]가 numbers[i +1] 보다 작은게 되어 위의 조건문에 알맞으므로 dp[i] = numbers[i + 1] 으로 갱신이 된다.
이 때, dp 배열은 [-1, -1, 5, -1] 이 된다.

 

위에 조건문의 반대 : numbers 배열의 현재 수가 다음 수 보다 크면

변수 j 에 i + 1 을 넣어준다.

dp[j] 즉, dp의 현재의 다음 수 가 -1 이 아닐 때의 조건으로 while문으로 반복문을 돌린다.

numbers 배열의 현재 요소가 dp 현재 다음 요소보다 크다면,

dp의 현재 수에 dp의 현재 다음 수를 저장한다.

위의 첫 조건문을 돌고 난 뒤에는 numbers[i]는 3, numbers[i +1]는 3 이기 때문에 처음 조건문에 알맞은 조건이 아니기 때문에 반대 조건문으로 들어가게 된다.
dp[j]는 현재 5 이다.
dp[j]가 -1 이 아닐 때 계속 반복해서 찾아야하기 때문에 while문을 이용한다.
numbers 현재 수 3이 dp 현재 다음 수 5 보다 작기 때문에 
dp 배열의 현재 수는 5가 된다.
j ++ 을 한 이유는 dp 배열의 현재 다음 수 부터 계속 큰 수가 있는지를 봐야하기 때문에 j++을 해주었다.