[프로그래머스 - JS] level.2 뒤에 있는 큰 수 찾기 📌⭐️⭐️

 

프로그래머스

---

나의 풀이 

오랜만에 풀리지 않는 문제를 만났다.  

구현을 정말 쉽다 바로 되지만 제출하면  몇몇 테스트 케이스가 '시간초과'가 발생하여 다시 코드를 작성해야 했다. 

 

 

초기 코드

function solution(numbers) {
    const save = {
        number : null,
        maxNumber : null
    }

    return numbers.map((number,index,arr) => {
        if(number === save.number) return save.maxNumber 
        let nextIndex = index + 1
        while(number >= arr[nextIndex]) nextIndex+=1
        if(arr[nextIndex]){
            save.number = number
            save.maxNumber = arr[nextIndex]
            return arr[nextIndex]
        } 
        save.number = number
        save.maxNumber = -1
        return -1
    })
}

이미 계산한 값들은 저장해서 다시 계산할 필요가 없도록 하였지만 제한적이었다.  

아직 DP구현이 완벽하지 않은 것 같다.  

위 코드는 `[ 999999, 999998, 999997, 999996,999995 ... 80만개 ..... 9000, 1000000] 이런식으로 되어있으면 전부 while이 동작하기에 불가능한 코드이다.  이걸 예외처리한다고해도 다른곳에서 문제가 생긴다.  

 

 

 

 

정답 코드 1

이 코드는 다른 분 블로그를 참고하면서 풀었던 코드이다. 

function solution(numbers) {
    const result = new Array(numbers.length).fill(-1);
    const stack = [];
    for (let i = 0; i < numbers.length; i++) {
        while (numbers[i] > numbers[stack.at(-1)]){
            const index = stack.pop()
            result[index] = numbers[i];
        }
            
        stack.push(i);
    }
    return result;
}

 

이전값이 현재값보다 크거나 같으면 stack안에 index를 전부 넣어 놓고 

현재값이 이전값보다 크면 stack에 있는 모든 index를 꺼내서 현재값으로 바꿔준다. 

 

 

정답 코드 2

DP로 푸신분도 있으셔서 가져왔다.

구현하는 방식을 공부하자!

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);   

    for(int i = numbers.size() - 2; i >= 0 ; i--)
    {
        for(int j = i + 1; j < numbers.size(); j++)
        {
            if(numbers[i] < numbers[j])
            {
                answer[i] = numbers[j]; 
                break;
            }
            else if(numbers[i] >= numbers[j])
            {
                if(answer[j] == -1)
                {
                    answer[i] = -1;
                    break;
                }     
                else if(numbers[i] < answer[j])
                {
                    answer[i] = answer[j];
                    break;
                }
            }
        }
    }  
    return answer;
}

이렇게 푸신분이 있어서 js로 바꾸고 리팩터링을 아래처럼 해주었다.

 

function solution(numbers) {
  let answer = Array(numbers.length).fill(-1);

    // 뒤에서부터 차례대로 순회한다.
    // j 는 i보다 한칸 앞이다. 
  for (let i = numbers.length - 2; i >= 0; i--) {
    for (let j = i + 1; j < numbers.length; j++) {

        if (numbers[i] < numbers[j]) {
            answer[i] = numbers[j];
            break;
        }
        
        // 나보다 더 큰 숫자 없다는 뜻
        if (answer[j] === -1) break;
        
        // 같은숫자가 중첩으로 있을 때 불필요한 계산을 막기위해
        if (numbers[i] < answer[j]) {
            answer[i] = answer[j];
            break;
        }
    }
  }
  return answer;
}