큰 수 만들기

// 강의를 보니까 강사님은 stack에 첫 번째 값을 넣지 않고 진행했더라고요.
// 저는 stack[stack.length-1]이 존재하지 않아서 number[i]랑 비교하면 오류가 날 것 같아서 초깃값으로 넣어줬는데
// stack이 빈 배열일 때 stack[stack.length-1] < number[i] 이 조건문이 false가 나오는 이유가 궁금하네요..

function solution(number, k) {
    const stack = []; // 스택 생성
    let cnt = 0; // 몇 개를 지웠는지 확인하는 카운트
    stack.push(number[0]); // number의 첫번째 값을 넣어줌
    
    for(let i = 1; i < number.length; i ++){
        // 현재 number의 값이 stack에 있는 마지막 값과 비교해서 더 크면 계속해서 pop을 해줌
        while(cnt  < k && stack[stack.length-1] < number[i]){
            stack.pop();
            cnt++; // 제거하면 카운트 증가
        }
        stack.push(number[i]); // stack에 현재 number 값을 push
    } 
    
    // cnt가 k만큼 제거되지 않았다는 건 뒤로 갈수록 숫자가 작아진다는 뜻이므로 남은 수만큼 stack에서 뒷 요소를 제거
  if(cnt < k){
    for( let i = cnt; i < k; i ++){
        stack.pop();
        cnt++;
    }
  }
    
    return stack.join("") // 합쳐서 리턴
}

function solution(number, k) {
    // 스택에 이용할 빈 배열을 만들어준다.
    const arr = [];
    // 반복문을 돌며 arr의 마지막값과 number의 현재값을 비교하고 k값이 0보다 큰지 확인한다.
    // arr의 마지막 값이 number의 현재값보다 작고 k값이 0보다 크다면 while문으로 들어간다.
    // arr의 마지막 값을 pop해주고 k값을 -1 해준다.
    // 아니라면 arr에 number의 현재값을 push해준다.
    for (let i = 0; i < number.length; i++) {
        while (k > 0 && arr[arr.length - 1] < number[i]) {
                arr.pop();
                k--;
        }
        arr.push(number[i])
    }
    
    // 위의 로직을 실행했을때 마지막 케이스가 통과 되지않아서 해설강의를 시청하고 예외처리가 되어있지 않았던것을 알게되었습니다.
    // ex) '98765' 
    // 예외처리를 위해 k값이 0이 아닐경우 while문을 돌려봤는데
    // pop만 해주고 k값을 빼주지않는 로직으로 반복문을 돌려서 무한 루프가 돌아가게되었고 
    // 역시나 마지막 케이스에서 시간초과가 떳습니다. 결국 구글검색을 해보니
    // splice함수로 뒷자리를 잘라주는 로직을 활용하는 방법도 있다는것을 알게되었습니다.
    // splice를 쓰지않고 밑에 while문 로직에 k--;를 넣어주면 통과 됩니다!
    
    // while (k !== 0) {
    //     arr.pop();
    // }

    arr.splice(arr.length - k, k);
    return arr.join('');
}

function solution(number, k) {
    let num =number.split("");
    let answer=[];
    //제거 기준은 뒤에 있는 값보다 앞에 있는 값이 작다면 앞에 있는 값을 제거, 제거시 그 앞 인덱스도 다시 확인, 
    // 종료 기준은 k==0이 될때, 다 돌고 k가 남았을때는 끝에서 부터 잘라준다. 
    
    for(let i =0; i<num.length; i++){
        // 스택을 이용해서 top을 pop하던지, 유지하던지 
        // answer가 0이라면 일단 넣고, 아니라면 top 과 현재값을 비교
        if(answer.length>0){
            // k가 남아있고, answer의 top이 현재 숫자보다 작다면 pop 그리고 k도 -1 해주고, 
            //i도 -1 해주어서 인덱스 유지, 아니라면 answer에 현재 숫자를 넣어준다. 
            if(k>0 && answer[answer.length-1]<num[i]){
                answer.pop();
                k--;
                i--;
            }else{
                answer.push(num[i]);
            }
        }else{
            answer.push(num[i])
        }
 
    }
    // k가 0 이 아니라면 끝에 k 만큼 잘라준다. (감소하거나 같은 수열이라 앞을 자르면 무조건 더 작아진다.  )
    return k===0 ? answer.join(""): answer.slice(0,-k).join("");
    
}

// 구해야 하는 가장 큰 숫자는 (number.length - k) 자리의 수입니다.
// 첫째 자리부터 한 자리씩 채워나갑니다. 채울 때마다 기존 number에서는 해당 숫자를 포함한 앞 부분은 모두 제거합니다.
// ex) 1231234
function solution(number, k) {
    var answer = '';
    const numberArr = Array.from(number);
    const answerLength = numberArr.length - k;
    let currentIdx = 0;
    while (answer.length < answerLength) {
        const max = numberArr.slice(0, numberArr.length - (answerLength - answer.length) + 1).sort((a, b) => b - a)[0];
        answer = answer.concat(max);
        currentIdx = numberArr.indexOf(max);
        numberArr.splice(0, currentIdx + 1);
    }
    return answer;
}
// 테스트 케이스 8,9,10 시간 초과가 나네요 ㅜ.ㅜ

function solution(number, k) {
    let answer = '';
    let cnt = 0;
    const stack = [];
    
    for(let x of number){
				// 스택이 비어있거나 제거할 개수만큼 모두 지웠다면 스택에 요소를 넣어줍니다.
        if(!stack.length || cnt === k) stack.push(+x);
				// 스택의 맨 위 요소가 x보다 크거나 같다면 스택에 요소를 push 합니다.
        else if(stack[stack.length - 1] >= +x) stack.push(+x);
        else{
						// 만약 스택 맨 위 요소가 x보다 작다면 x와 같거나 큰 값이 나올때까지
						// 스택을 pop 합니다. 
            while(stack.length && stack[stack.length - 1] < +x && cnt < k){
                stack.pop();
                cnt += 1;
            }
						// 다 지우고 나서 x를 스택에 넣어줍니다. 
            stack.push(+x);
        }
    }
    
		// 스택에는 k개만큼 지워지지 않은 숫자가 들어갈 수 있습니다.
		// 만약 그 얘기는 모두 중복값이거나 내림차 순으로 정렬된 수라는 뜻이므로
		// 첫째자리부터 k개만큼 지워지도록 잘라줍니다.
    return stack.join("").slice(0, number.length - k);
}

// 어떤 수가 있을때 나보다 높은 자릿수에 더 작은 숫자가 왔을경우 그 숫자는 무조건 지워야 합니다.
// "111119" 의 경우 9 앞의 1을 가능한 최대로 지우는게 정답이 됩니다.

/*
1️⃣접근: 가장 큰 숫자를 발견해서 앞 뒤로 빼야하는 개수만큼 빼버리는 방법 => 문제 의도와 전혀 맞지 않음
2️⃣접근: 차례대로 앞의 숫자들과 비교해서 작은값들을 없애고 그것을 count해서 멈추게 만드는 방법
				-> 테스트 케이스3부터 문제가 생김. 테스트 케이스3의 앞의 큰 숫자 7도 없어짐😱😱
3️⃣접근: 힌트(stack) 얻고 stack 사용
*/ 

//2️⃣접근 splice()안쓰고 첫시도. 바로 테스트 케이스 3 실패 ❌❌
function solution(number, k) {
  let cnt = 0;
  const arr = number.split("");

  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] !== "" && arr[j] < arr[i]) {
        arr[j] = "";
        cnt += 1;
        console.log(cnt, arr);
        if (cnt === k) {
          return arr.join("");
        }
      }
    }
  }
}

//3️⃣접근 - stack 이용
function solution(number, k) {
    let cnt = 0;
    const result = [];
    
    for(let i = 0; i <number.length; i++){
        
        //stack의 top과 number[i]를 비교해서 top이 작으면 stack에서 pop해준다.
        while(number[i]> result[result.length-1] && cnt < k){
            result.pop();
            cnt++
        }
        
        //처음부터 넣어주면 다른 결과값이 나온다.특히 테스트 Case1같은 경우 top이 9가 되서 틀린 답이 나옴
        //갯수를 채워주도록 뒤에 위치시켜야한다.
        if(result.length < number.length -k){
            result.push(number[i]);
        }
    }
    
    return result.join('');
}