1. 가장 큰 수 구하기

바로 예시를 통해서 배워보자.

  number      k    return 값
"1924"	      2	   // 94
"1231234"	  3	   // 3324
"4177252841"  4    // 775841

이렇게 정보가 주어졌을때 k만큼 number에서 숫자를 제외하고 나머지 숫자의 갯수들로 숫자를 조합한다고 했을때, 만들어 질 수 있는 숫자중 가장 큰 수를 리턴하면 된다. 그럼 return 값 처럼 결과가 출력된다.

이때, number안에 배열되어있는 숫자의 순서를 지켜야 한다. 1315294, 3 이라고 할때 5294는 되지만 5924는 되지 않는다. 어짜피, 조합이기 때문에 배열은 신경쓰지 않지만 혹시나 헷갈릴까봐 미리 언급을 해둔다.

2. 접근 방법

2-1. 조합구현

우선 조합이 가장 먼저 떠올랐다. k만큼 제외한 숫자들을 조합으로 만든다음 그 중에 가장 큰 수를 max를 이용해서 뽑아내면 되는 거다.

조합은 그 전에도 배웠었다. 하지만 그때는 조합의 갯수만 리턴했을뿐 실제 조합이 어떠한 원소로 이루어져있는지는 볼 수 없었다. 이번에는 실제 모든 조합을 다 배열에 담아 리턴해야한다.

구글링 해보니깐 획기적으로 구현해놓은 코드가 있어서 설명해보려고 한다.

원리는 같다. [1,2,3,4,5] 중에서 4개의 숫자를 뽑는다고 할때 1개를 고정시켜놓고 4개중에 3개를 뽑는 조합을 구한다. dfs에 4개의 원소로 이루어진 배열과 뽑는 갯수(3)를 pass한다.

그리고 다시 원소의 갯수를 하나 줄이고 뽑는 갯수도 하나 줄인다.

이렇게 해서 뽑는 갯수가 1이 되었을때 고정된 숫자에 각각의 원소를 하나 뽑아서 더한 다음 배열에 담아서 리턴한다.

그럼 그 리턴된 배열에 또 고정된 숫자를 그대로 연결해서 리턴한다.

이런식으로 다시 올라가면서 리턴하게 된다. merge sort하는 방법이랑 살짝 비슷하다고 보면 될 거 같다.(arr를 최소단위까지 쪼갠다음 합치고 합치는 관점에서 본다면)

근데, 모든 조합의 경우를 구하지 않아도 된다.(항상 불필요한 반복을 줄이는 연습을 하자. 좀 더 읽기 쉽고 효율적으로 만들 수 없는지 항상 질문하자!!!) 앞자리가 가장 큰 숫자로 이루어진 조합만 구하면 된다. 따라서0 ~ number.length-k 범위안에서 가장 큰 숫자를 찾은다음에 dfs에 같이 넘겨준다.

그리고 dfs안에서 가장 큰 숫자보다 작은 수는 그냥 pass하면 된다. 그럼 코드를 구현해보자!

const getCombinations = function (arr, selectNumber, biggestNum = 0) {
  const result = [];

  if (selectNum === 1) return arr.map((value) => [value]);

  arr.forEach((fixed, index, origin) => {
    if (fixed >= biggestNum) {
      const rest = origin.slice(index + 1);
      const combinations = getCombinations(rest, selectNum - 1);
      const attached = combinations.map((combination) => [
        fixed,
        ...combination,
      ]); // 돌아온 조합에 떼 놓은(fixed) 값 붙이기
      results.push(...attached); // 배열 spread syntax 로 모두다 push
    }
  });

  return results;
};

function mySolution(number, k) {
  let numberArr = number.split("");
  let selectNum = number.length - k;
  let biggestNum = 0;
  let max = 0;

  for (let i = 0; i < k; i++) {
    biggestNum = Math.max(numberArr[i], biggestNum);
  }

  let result = getCombinations(numberArr, selectNum, biggestNum);
  result.forEach((comb) => (max = Math.max(comb.join(""), max)));

  return max;
}

그럼 아래와 같은 인자를 pass했을때 다음과 같은 결과가 나온다.

mySolution('12345',2)
345

getCombinations([1, 2, 3, 4, 5], 4);
0: (4) [1, 2, 3, 4]
1: (4) [1, 2, 3, 5]
2: (4) [1, 2, 4, 5]
3: (4) [1, 3, 4, 5]
4: (4) [2, 3, 4, 5]

getCombinations([1, 2, 3, 4, 5], 4, 2);
0: (4) [2, 3, 4, 5]

정말 깔끔하다...getCombinations([1, 2, 3, 4, 5], 4)가 실행된다고 했을때 그 과정을 그림으로 그려보았다.

잘 보면 맨 끝의 가지에서 하나씩 arr가 합쳐지면서 조합이 완성되어가는 것을 볼 수 있다.

그리고 biggestNum가 0으로 default되어있는데 값을 입력하면 biggestNum아래의 값으로 시작되는 조합은 dfs를 시작하지 않고 지나쳐버린다.

그리고 만들어진 조합을 join으로 묶어서 가장 큰수를 return 하면 끝!

근데 dfs가 있어서 그런지 최종테스트에서 런타임에러가 나기 일수다. 더 탐욕스럽게 코드를 짜보자!

2-2. 더 탐욕스러운 코드

dfs를 쓸 필요 없이 for문과 while문 2개의 반복문으로 끝낸다.

• pseudo code

  • number의 숫자 개수에서 k의 갯수만큼 점점 깎아내려간다 생각하면 됨

  • stack안의 숫자가 바뀔 때 마다(pop이 될 때 마다) number에서 깎아낸다고 보면 된다.

  • 깎아내는 이유는 다음숫자가 이전의 숫자보다 더 크기 떄문이다.

  • 이전의 숫자중에 큰 숫자까지 전부 깎아낸다.

  • 혹시나 k가 남았다고 할때(아직 k만큼 깎아내야한다) stack의 마지막에서 k만큼 깎아내면 됨.

그럼 코드로 구현해보자.

function otherSolution(number, k) {
  const stack = [];
  let answer = "";

  for (let i = 0; i < number.length; i++) {
    const eachNum = number[i];
    while (k > 0 && eachNum > stack[stack.lenth - 1]) {
      stack.pop();
      k--;
    }

    stack.push(eachNum);
  }

  answer = stack.splice(stack.length - k, k).join("");

  return answer;
}

그럼 그림으로 그 과정을 나타내보자!

보면 k만큼 지워나가는 것을 볼 수 있다. 그리고 지워나가면서 가장 큰 수만 남는것을 알 수 있다.

3. 탐욕법인 이유?

가장 큰 수를 뽑고 그 다음 큰 수를 뽑아서 이어붙인다.

그럼 이어붙인 수가 가장 큰 수이기 때문에 탐욕법이 된다. 부분의 최적해가 전체의 최적해가 되므로.

와 이해했다. 이해했어!! 내것이 되었다. 이런식으로 내것으로 차근차근 받아들이자.