[프로그래머스][LEVEL2] 큰 수 만들기

# 문제 원문

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

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

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

제한 조건

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

입출력 예

number / k / return

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

출처

# 문제 풀이

 

간단한 문제 같아서 가볍게 접근했다가 시간낭비 엄청나게 한 문제.. 간단한 것도 극한 상황이 되면 헬이라는걸 느끼게 만들어줬다. 주어진 문자열 number를 일정 수 만큼 잘라서 가장 큰수를 비교 하는 방식으로 진행했더니 9번 10번 테스트 케이스에서 런타임 에러가 나오는데 아무리 해도 문자열을 건드는 순간 답이 안나와서 삽질을 멈추고 접근 방법을 조금 수정했다. 가장 큰수를 구하는 문제이기 때문에 앞의 부분에서 부터 가장 큰수가 오는 선택을 반복하면 되는 문제이지만 문제 자체의 함정인 극한 값 + 자를 이유가 없는 경우에도 잘라야 한다는 것등 여러가지 면에서 공들여서 만들어진 테케들이 많아서 주의를 기하지 않으면 이게 맞는데 왜 틀려? 를 반복하면서 시간을 잡아 먹는 문제이다.

 

# 솔루션 플로우

1. 입력 받은 문자열 number를 배열로 만들고 순회한다.

2. 얻어진 숫자 current를 result 배열에 들어가 있는 수들과 대소 관계를 비교한다.

3. current가 더 크고 + 제거 하는 수 의 갯수가 0보다 크다는 조건을 만족하는 result 요소를 pop하면서 k를 그 수량만큼 감한다.

4. 2-3을 반복하면서 result의 length가 입력 받은 number.length - k의 길이 만큼 될때까지 current를 삽입한다.

5. 얻어진 배열 result를 조인해서 숫자로 이루어진 문자열 result를 얻는다.

6 얻은 result를 반환한다.

1. 스택을 활용한 풀이

function solution(number, k) {
    const length = number.length - k;
    return Array.from(number).reduce((result, current) => {
        while (result.length > 0 && result[result.length - 1] < parseInt(current) && k > 0) {
            result.pop();
            k--;
        }
        result.length < length && result.push(parseInt(current));

        return result;
    }, []).join('');
}