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

문제 설명

---

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

• 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
• 문자열 형식으로 숫자 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"

내가 푼 답

---

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

  for (let i = 0; i < number.length; i++) {
    const current = number[i];

    while (k > 0 && Arr1.length > 0 && Arr1[Arr1.length - 1] < current) {
      Arr1.pop(); 
      k--;
    }
    Arr1.push(current); 
  }

  if (k > 0) {
    Arr1.splice(-k, k);
  }

  return Arr1.join(''); 
}

Code Flow

---

생각하기

• number는 백만자리 미만의 자연수고, k가 number.length 미만일때, 가장 큰 수를 만들어야한다.
• 그렇다면 greedy가 맞다. 처음숫자 가장 큰거, 그 다음 큰거, 그 다음 큰거, 그 다음 큰거 식으로 진행된다.
• 처음에 자른 배열 중에서 가장 큰수가 들어가고, 그다음 큰 수, 그리고 그 다음 큰 수가 들어간다.
• 근데 여기서 주의해야 할 점은, k만큼 빼내야하므로 k카운트가 가득차면 더이상 빼낼 수 없다는 점임.
• 예시1을 예시로 보자, (...number) 했을때, 9,4가 들어가야하며, 이는 가장 큰 수부터 차례대로 빼내는게 맞다.
• 예시2를 예시로 보자, (...number) 했을때, 4가 먼저 나와야하지만, 4를 빼냈을 때 뒤가 없으니까, 3이 나와야한다.
• 그렇다면 k 카운트만큼 뒤의 배열이 남기도 해야함. 예시 2의 경우 234. 그러니 K를 하나씩 빼주자.
• 예시3을 예시로 보자, (...number) 했을때, 7이 먼저 들어가야하는데, 4가 먼저 들어갈 거다. , 그 뒤에 쭉 배열카운트보다 작은것들을 제외해준다

문제점 : k가 남았을때는 어떻게 해야할까?

• k가 0보다 크다면, 뒤에서부터 k를 봐서 가장 작은거부터 지워주게 한다. splice()함수를 이용해도 되고, lastindexOF를 사용해도 된다.
• 예시3을 풀이방법대로 풀면, "7" "7", "2", "5", "2", "8", "4", "1" 가 남는다, 이 경우엔 뒤에서부터 "1", "2"가 지워진다.

풀이를 좀 더 간결하게 해보자.

---

다른 해답은 없을까?

---

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

    answer.push(number[head++])
    while(answer.length < number.length - k || head < number.length) {
        if(del && answer[answer.length-1] < number[head]) {
            answer.pop()
            del--
            continue
        }
        answer.push(number[head++])
    }

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

• 기본적인 방법은 동일하되, 마지막에 slice를 통해 완성해주었다.