프로그래머스[Level2] 큰수 만들기 -Javascript

문제 설명

문제 링크

[프로그래머스[Level2] 큰 수 만들기]
(https://school.programmers.co.kr/learn/courses/30/lessons/42883)

접근 방법

1. 매 순간 최적을 생각하는 그리디로 일정 범위 내에서 가장 큰 수를 찾기(테케10,시간 초과)

   for문을 0~numberOfDigits 필요한 범위만큼 설정
   안쪽의 for문에서는 k+i만큼 범위를 설정 (why?)
   startIndex의 변화로 현재 가장큰수 찾고 그 다음 인덱스를 시작 Index로 설정

2. 최소한의 변수 선언으로 최적의 해 도출하기

   주어진 number 배열의 길이만큼 for문을 구성
   while문을 사용하여
   1)k>0 -> 주어진 k만큼 while문을 돌리며
   2)answer[answer.length-1] < number[i]

   -> answer 배열의 맨뒤 원소값을 현재 number[i]와 계속해서 비교하여
   number[i]보다 작은경우 빼주기 위해서 ex) 4 1 7 ...=> 4 7  => 7

   answer.join("")으로 배열형식을 String 형식으로 조절
   .slice(0,number.length-k) 는 ex) "666","44444",... 등 연속되는 숫자인 경우
   while문 루프를 돌지 않고 push만 하기 때문에 원하는 자릿수만큼 결과를 리턴하기 위함

   코드

function solution(number, k) {
    var answer = '';
    // return 받을 자리수 
    let numberOfDigits =  number.length - k ;
    let startIndex = 0;

    for(let i=0;i<numberOfDigits; ++i){
        let maxValue = -1;
        let maxIndex = 0;
        // 범위 설정 이유 :
         ex) "4177952841" ,k = 4 인 경우 원하는 자릿수 6으로
             4 1 7 7 9 | 5 2 8 4 1
                     ↑  
             앞쪽에서 k+1 범위 내에서 가장 큰 수 : 9 , index : k+1 나머지 5자리를 붙여서 만들어야 하기때문에
        for(let j=startIndex; j<=k+i;++j){
            if(maxValue<parseInt(number[j])){
                maxValue = number[j];
                maxIndex = j;
            }
        }
        startIndex = maxIndex+1; 
        answer+=maxValue
    }
    return answer;
}
// 테케 10 : 시간 초과

function solution(number, k) {
    var answer = [];
    for (let i=0;i<number.length;++i){
        while(k>0&&answer[answer.length-1]<number[i]){
            answer.pop();
            k--;
        }
        // answer : 1  number[1] = 9
        // answer : (1) 9  number[2] = 2
        // answer : (1) 9 2 number[3] = 4
        // answer : (1) 9 (2) 4
        answer.push(number[i]);
    }
    // ex) 똑같은 수 나올 경우 "333" while 문에 들어가지 않고 "333"을 전부 return 하게 되기 때문에 원하는 문자열 만큼을 리턴하게 만들어줌 
    return answer.join("").slice(0,number.length-k);
}