[JS] 큰 수 만들기

그리디 문제입니다.

프로그래머스 level 2이고, 그리디 문제를 오랜만에 풀어서 그런지 생각이 바로 안나더라구요.

 

루프를 몇개 씩 돌려보다가 계속 런타임 에러가 나서 한 루프안에서 다 처리할 수 없을까? 하는 생각에 이래저래 해보다보니 어떻게 만들긴 했네요. 약간 가독성이 안좋아서 걱정입니다.

그럼 같이 보시죠!

---

문제 요약

 

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

 

제한 조건

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

 

테스트케이스

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

접근 방법

되게 여러 가지로 접근해봤습니다.

 

일단 배열을 k까지 잘라서 그 안에서 최댓값 빼고 모든 값을 제거하기.1부터 9까지 타겟을 잡고 number를 처음부터 순회하면서 제거하기.

 

많은 방식을 사용해봤었는데 결국엔 루프가 2중, 3중으로 생기면서 통과를 못하는 일들이 생겼습니다. 그 뿐만 아니라 에러도 많이 났습니다.

 

일단, 루프 한번에 끝낼 수 있는 방법으로 생각했습니다.

 

동작 순서

1. number를 처음부터 순회합니다.
2. 정답 스택의 마지막 값(end)과 현재 number 값(target)을 비교합니다.
   1. target 이 크다면, 정답 스택을 pop합니다. target <= end를 만족할 때까지 계속 pop을 해줍니다.
      이때, pop한 갯수를 세서 k값을 넘지 않도록 적절히 조절해줍니다.
      (ex, 테스트 3번 "4177252841"의 경우 7이 나올 때 까지 앞의 모든 값을 pop해줘야합니다.) 
      
      
   2. target이 더 작다면 pop한 값을 다시 push해줍니다.
3. target을 push해줍니다.

이렇게 하시면 일단 논리가 말이 됩니다.

코드 같이 보시죠.

 

정답 코드

function solution(number, k) {
    const answer = [0];
    let remainK = k + 1;
    let index = 0;
    for (index; index < number.length; index++) {
        const end = answer[answer.length - 1];
        const curr = Number(number[index]);
        if (curr > end) {
            while (remainK > 0 && answer.length > 0) {
                const val = answer.pop();
                if (val < curr) remainK--;
                else {
                    answer.push(val);
                    break;
                }
            }
            answer.push(curr);
            if (remainK === 0) break;
        } else {
            answer.push(curr);
        }
    }
    if (remainK > 0) {
        return answer.join("").slice(0, number.length - remainK);
    }
    return answer.join("") + number.slice(index + 1);
}

 

팁 1. 마지막 분기에 대해서

테스트 케이스 12번을 통과하지 못할 겁니다.다른 분 질문에서 힌트를 얻었습니다.number = "4321", k = 1, return = "432"의 케이스가 이 논리대로라면 그냥 "4321"을 리턴하게 됩니다.그래서 remainK가 0인지 확인을 꼭해주고, 아니라면 정답의 뒷부분에서 그 갯수만큼 떼어내줘야합니다.

if (remainK > 0) {
    return answer.join("").slice(0, number.length - remainK);
}

 

 

생각보다 오래걸렸네요. 되게 쉬워보이는데......

 

그럼 이만!