[프로그래머스] 큰 수 만들기 (Javascript)

박먼지·2023년 1월 10일
0

코딩테스트

목록 보기
15/23
post-thumbnail

💡 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

  • number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
  • k는 1 이상 number의 자릿수 미만인 자연수입니다.

내 풀이 📝

function solution(number, k) {
    var arr = number.split("").map(Number);
    var answer = "";
    var max = 0;
    var idx = 0;
    var temp = 0;
    var size = arr.length - k;
  
    while(answer.length < size){
    	for(let i = idx; i <= k; i++){
       		if(max < arr[i]){
          		max = arr[i];
          		temp = i;
       		}
    	}
     idx = temp+1;
     k++;
     answer += String(max);
     max = 0;
    }
    
  return answer;
}

무지성 풀이.. 이렇게 구하면
테스트 10 〉 통과 (3791.61ms, 55.6MB)
시간이 엄청 오래 걸린다!

다른 사람 풀이 💯

function solution(number, k) {
    const answer = [];
    let head = 0;
    let del = k;

    answer.push(number[head++]); // (1) number의 가장 왼쪽에 있는 숫자를 answer 배열에 넣음
  
    while(answer.length < number.length - k || head < number.length) {
        if(del && answer[answer.length-1] < number[head]) { // (3) del이 0보다 크고 number의 현재 위치의 숫자가 바로 왼쪽에 있는 숫자보다 클 경우
            answer.pop(); // (4) answer 배열에서 마지막 원소 제거
            del--; // (5) 제거한 수 count 
            continue;
        }
        answer.push(number[head++]); // (2) number의 그 다음 숫자들을 answer 배열에 넣음
    }

    return answer.slice(0, number.length - k).join('');
}

다들 스택 구조 쓰셨더라.. 스택은 생각도 못했는데.
이렇게 하면 속도가 훨씬 빠르다!

profile
개발괴발

0개의 댓글