[JS] Greedy - 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883#

프로그래머스

Question

어떤 숫자에서 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"

 

---

solution

직관적으로 생각해보면 큰수가 나올 모든 경우를 구해서 가장 큰수를 찾는 것이다.

하지만 제한조건으로 number는 백만자리라서 위의 방법은 불가능하다.

N이 백만이면 O(N), O(N log N)으로 구해야한다.

 

풀이 방법

1. 큰 값이 나오면 이전 값 중 더 작은 값들은 모두 삭제한다.

2. 즉, stack의 바닥에서부터 top은 큰 수부터 작은 수로 나열이 되어야한다.

 

먼저 스택 배열(stack)을 하나 만들고, 몇개를 지웠는지 카운팅을 해줄 변수(count)를 선언하자.

function solution(number, k) {
  const stack = [];
  let count = 0;
}

앞에서 받은 스트링 넘버를 순차적으로 순회를 하자.

그 안에 while문을 만들 후 count가 k보다 작을 때, 그리고 stack의 top에 해당하는 값보다 들어오는 값이 클 경우 순차적으로 지워주는 작업을 하자.

그렇다면 pop이 된 숫자는 작은 숫자일 것이고 다른 숫자들은 stack에 push를 해준다.

function solution(number, k) {
  const stack = [];
  let count = 0;
  
  for(const item of number) {
    while (count < k && stack[stack.length - 1] < item) {
      stack.pop();
      count++;
    }
    stack.push(item);
  }
}

이렇게 해주면 string은 왼쪽에서 오른쪽까지 큰수에서 작은수 순으로 나열 될 것이다.

 

stack.join('') 으로 return 을 해주자.

이렇게 되면 틀리는 test case가 생길텐데, k만큼 다 지워지지 않는 경우가 있기 때문이다.

function solution(number, k) {
  const stack = [];
  let count = 0;
  
  for(const item of number) {
    while (count < k && stack[stack.length - 1] < item) {
      stack.pop();
      count++;
    }
    stack.push(item);
  }
  
  return stack.join('');
}

만약 입력값으로 "9876543"이 들어오면 뒤에 수보다 작은 수가 없으니 stack이 아예 pop 되지 않는다.

이런 경우를 처리하기 위해 count가 k보다 작을 경우 계속 pop을 할 수 있도록 다시 한번 루프를 돌려주자.

 

function solution(number, k) {
  const stack = [];
  let count = 0;
  
  for(const item of number) {
    while (count < k && stack[stack.length - 1] < item) {
      stack.pop();
      count++;
    }
    stack.push(item);
  }
  
  while(count < k) {
    stack.pop();
    count++;
  }
  
  return stack.join('');
}

---

solution2

풀이방법

1. 정답이 될 수 있는 자리수를 알아낸다. "4177252841", 4 인경우 정답의 자리수는 6자리이다.

2. 정답의 가장 첫번째 수가 될 수 있는 숫자는 첫번째 자리의 수가 될 수 있는 범위에서 가장 큰 수를 구한다.

-> 정답의 각 자리수는 각각의 그 숫자가 될 수 있는 범위에서 가장 큰 수를 구한다.

"4177252841" 에서 정답은 6자리 수이므로 정답의 첫번째 숫자는 number의 index 0 ~ 4번째 범위의 숫자중 가장 큰 숫자이므로 7이다. 7은 number에서 index 2번이므로 정답의 그다음 자리수의 범위는 index 3 ~ 5번째 범위의 숫자중 가장 큰 숫자이다.

 

먼저 각 범위에서 가장 큰 숫자를 찾는 함수를 작성한다.

루프를 돌리는 중 숫자 9가 나오면 무조건 큰 숫자이니 루프를 멈추고 9를 리턴한다.

function solution(number, k) {
  const length = number.length;
  let answerL = length - k; // 정답 길이
  
  // 범위내에서 최댓값 구하기
  const getMaxNum = (startIdx, endIdx) => {
    let maxNum = -1;
    let maxIdx = -1;
    for(let i = startIdx; i < endIdx; i++) {
      const num = number[i];
      if(num === '9') {
        return ['9', i];
      }
      if(num > maxNum) {
        maxNum = num;
        maxIdx = i;
      }
    }
    return [maxNum, maxIdx];
  }
  
}

정답이 될 answer에 숫자를 하나하나씩 추가해 나갈 것이며 정답의 길이 (answerL)은 하나씩 줄여나갈 것이다.

그리고 answer에 추가하지 않고 지나쳐갈 숫자는 k의 갯수와 같아야하므로, answer에 추가될 숫자가 하나하나씩 정해질 때마다 k의 갯수도 지나간 숫자만큼 줄여나간다.

따라서 정답의 길이 (answerL)이 0보다 클 경우 루프를 돌려준다.

 

범위의 첫번째 값은 start로, 마지막 값은 end로 선언하는데, end는 start + k + 1이다.

function solution(number, k) {
  const length = number.length;
  let answerL = length - k; // 정답 길이
  
  // 범위내에서 최댓값 구하기
  const getMaxNum = (startIdx, endIdx) => {
    let maxNum = -1;
    let maxIdx = -1;
    for(let i = startIdx; i < endIdx; i++) {
      const num = number[i];
      if(num === '9') {
        return ['9', i];
      }
      if(num > maxNum) {
        maxNum = num;
        maxIdx = i;
      }
    }
    return [maxNum, maxIdx];
  }
  
  let answer = '';
  let start = 0;
  let end = k + 1;
  
  while(answerL > 0) {
    const [maxNum, maxIdx] = getMaxNum(start, end);
    answer += maxNum;
    start = maxIdx + 1;
    end = start + k + 1;
    k = k - (maxIdx - start);
    answerL--;
  }
  
}

answer 이 다 채워지기도 전에 k가 0이 되는 경우 (더이상 숫자를 지울 필요가 없는 경우) number에서 나머지 뒤에 있는 숫자들을 붙여주고 while문을 빠져나오기 위해 if문을 하나 추가한다.

 

function solution(number, k) {
  const length = number.length;
  let answerL = length - k; // 정답 길이
  
  // 범위내에서 최댓값 구하기
  const getMaxNum = (startIdx, endIdx) => {
    let maxNum = -1;
    let maxIdx = -1;
    for(let i = startIdx; i < endIdx; i++) {
      const num = number[i];
      if(num === '9') {
        return ['9', i];
      }
      if(num > maxNum) {
        maxNum = num;
        maxIdx = i;
      }
    }
    return [maxNum, maxIdx];
  }
  
  let answer = '';
  let start = 0;
  let end = k + 1;
  
  while(answerL > 0) {
    const [maxNum, maxIdx] = getMaxNum(start, end);
    answer += maxNum;
    start = maxIdx + 1;
    end = start + k + 1;
    k = k - (maxIdx - start);
    answerL--;
    
    if(k === 0) {
      answer += number.slice(start);
      break;
    }
  }
  
  return answer;
}

이렇게 하면 number가 "000001000" 이며 k 가 3일 경우 "1000"이 정답으로 나와야하는데, "001000"이 정답으로 나오게 된다.

이걸 방지하기 위해서 maxNum이 0이면 answer의 첫번째 자리에 오지 못하도록 while문 위쪽에 if문 하나를 더 추가하자

function solution(number, k) {
  const length = number.length;
  let answerL = length - k; // 정답 길이
  
  // 범위내에서 최댓값 구하기
  const getMaxNum = (startIdx, endIdx) => {
    let maxNum = -1;
    let maxIdx = -1;
    for(let i = startIdx; i < endIdx; i++) {
      const num = number[i];
      if(num === '9') {
        return ['9', i];
      }
      if(num > maxNum) {
        maxNum = num;
        maxIdx = i;
      }
    }
    return [maxNum, maxIdx];
  }
  
  let answer = '';
  let start = 0;
  let end = k + 1;
  
  while(answerL > 0) {
    const [maxNum, maxIdx] = getMaxNum(start, end);
    if(answer.length === 0 && maxNum === 0) {
      answer += '';
    } else {
      answer += maxNum;
    }
    
    answer += maxNum;
    start = maxIdx + 1;
    end = start + k + 1;
    k = k - (maxIdx - start);
    answerL--;
    
    if(k === 0) {
      answer += number.slice(start);
      break;
    }
  }
  
  return answer;
}