큰 수 만들기 (탐욕법, 프로그래머스)

큰 수 만들기

📌 문제 설명

• 어떤 숫자에서 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.length - k 갯수 만큼의 중복되지 않은 가장 큰 수를 만들면 된다고 생각했다.
그래서 DFS를 통해 순서가 없는 가장 큰 수를 만들어 보고자 했다.

	function solution(number, k) {
  let answer = Number.MIN_SAFE_INTEGER;

  let numberLength = number.length - k;
  let ch = Array.from({length: number.length}, ()=> 0);
  const DFS = (L, sum) => {
      if ( L === numberLength) {
        console.log(sum)
        answer = Math.max(answer, sum)
      }
      else {
          for ( let i = 0; i <= number.length; i++ ) {
              if ( ch[i] === 0 ) {
                  ch[i] = 1;
                  DFS(L+1, sum + number[i])
                  ch[i] = 0
              }
          }
              
      }
  }
  DFS(0, 0)

  return answer
}


console.log(solution("1924", 2)) // "94"
console.log(solution("1231234", 3)) // "3234"
console.log(solution("4177252841", 4)) // "775841"

😵‍💫 수를 만들고 코드를 돌려 값을 보고 나서야 잘못되었음을 깨달았다.

즉, 내가 만든 수는 중복되지 않으며, 순서를 고려하지 않은 조합 중에 가장 큰 수인 조합이고, 문제에서 제시한 것은 순서를 고려한 가장 큰 수인 순열 이다.
또한 고려해야 할 점은 복잡도를 최소로 하기 위해 탐욕법을 적용해 O(n) 시간 복잡도를 사용해야 한다.
따라서 for문을 통해 한번 씩 탐색을 하고 스택에 해당 수를 푸쉬하고 이전 숫자보다 작은 숫자의 경우 제외 및 k의 수를 1씩 감소시키는 코드를 적용했다.

function solution(number, k) {
    const stack = [];

    for ( let i = 0; i < number.length; i++ ) {
        const el = number[i];
        while ( k > 0 && stack[stack.length - 1] < el ) {
            stack.pop();
            k--;
        }
        //  stack.push(el);
        // 동일한 수가 연속되었을 때 모든 수가 푸쉬되는 경우를 제외하기 위해
        // number.length에서 k만큼 제거 된 숫자가 스택안에 존재하는 경우는
        // 더 이상 푸쉬 하지 않는다.
        if (stack.length < number.length - k ) stack.push(el);
    }
    // console.log(stack)
    console.log(k)
    return stack.join('');

}

// console.log(solution("1924", 2)) // "94"
// console.log(solution("1231234", 3)) // "3234"
// console.log(solution("4177252841", 4)) // "775841"
// console.log(solution("55555", 2)) // "555"

// 테스트 케이스에는 없는 예외 케이스
// console.log(solution("333355", 3)) // "355"

💡 하지만 아무런 조건 없이 스택에 숫자를 넣는 경우 동일 한 수가 연속적으로 나올 경우 while문 안의 조건에 들어가지 못해 k에 관계 없이 스택에서 pop() 되지 못하는 상황이 발생한다. (테스트 12 실패)

이를 충족시키기 위해 스택 안에 제시된 숫자만큼의 수가 들어간 경우에는 다음 수가 스택에 들어가지 못하는 조건을 추가해주었다.