[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 큰 수 만들기

📌  문제

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

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

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

📌  제한사항

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

---

📌  풀이

알아야 하는 것

• str.split() : 문자열을 지정한 구분자를 기준으로 나눈다.
  • 괄호 안에 아무 것도 넣지 않으면 전체 문자열이 요소 1개가 되어 배열 안에 들어간다. (ex. "1924" -> ['1924'])
  • 괄호 안에 ""를 넣으면 문자열의 요소, 즉 글자 단위로 각자 쪼개진다. (ex. "1924" -> ['1', '9', '2', '4'])
• arr.join() : 배열의 모든 요소를 연결해 하나의 문자열로 만든다.
  • 괄호 안에 아무 것도 넣지 않으면 구분된 쉼표까지 묶여 문자열이 된다. (ex. ["안", "녕"] -> 안,녕)
  • 괄호 안에 ""를 넣으면 요소들만 묶어 문자열이 된다. (ex. ["안", "녕"] -> 안녕)

구할 것

예를 들어 "1231234"가 주어졌고, 3개를 제거할 수 있다고 하자. 리턴값은 "3234"다.

 

문자열을 먼저 split으로 쪼개 arr = ["1", "2", "3", "1", "2", "3", "4"]로 만들어 놓는다.

큰 수라고 하면 앞 자리 숫자가 커야 한다. 뒷자리 숫자는 그다지 중요하지 않다.

 

리턴값을 비교해보면 아마 맨 앞의 1과 2 / 첫 번째 3 뒤의 1 이 지워졌음을 알 수 있다.

뒤 값과 비교해서 더 큰 값을 갱신하고, 갱신할 때마다 k에 -1을 더해 k가 0이 되면 멈추는 형태이다.

 

이를 구현하기 위해 for문 + stack + while문을 사용한다.

 

for문으로 arr를 순회하면서 일단 stack에 push한다.

1번째 인덱스부터 값을 비교해보자.

 

stack = ["1"] / 비교 대상 "2" / k = 3

비교 대상이 더 크기 때문에 stack에 있는 값을 pop하고 새로운 값을 push한다.

하나를 삭제했으니 k-= 1을 하면 k = 2가 된다.

 

즉 arr[i]가 stack[stack.length-1]보다 클 경우, stack.pop() k-- 를 하고 해당 값을 push한다고 쓸 수 있다.

 

stack = ["2"] / 비교 대상 "3" / k = 2

똑같이 비교했을 때 3이 더 크므로 pop을 하고 k를 -1 한 후 새로운 값을 push한다.

 

stack = ["3"] / 비교 대상 "1" / k = 1

stack에 있는 값이 더 크다. "1" 다음 값과 비교해 갱신할 수 있도록 일단 push한다.

 

stack = ["3", "1"] / 비교 대상 "2" / k = 1

stack[stack.length-1]보다 비교 대상 "2"가 더 크다. pop을 하고 k를 -1 하고 이 값을 push한다.

 

stack = ["3", "2"] / 비교 대상 "3" / k = 0

k가 0이 되어 더 이상 무언가를 비교하고 삭제할 수 없다. 이대로 쭉 for문을 순회하며 push한다.

 

최종적으로 stack = ["3", "2", "3", "4"]가 되었다.

문제에서 문자열 형태로 리턴하라고 했으니 join() 메서드를 사용해 이들을 문자열로 묶어서 리턴한다. 

 

그런데

상대는 그리디다... 분명 생각 못한 함정이 있을 것임.

3번째 테스트 케이스인 "4177252841", 4를 해보자.

 

stack = ["4"] / 1 비교 / k = 4

-> 4가 더 크니 대체되지 않고 그대로 push한다.

 

stack = ["4", "1"] / 7 비교 / k = 4

 

** while문에서 k > 0 && stack[stack.length-1] < arr[i] 라고 적었다.

현재 7이 2번 연속으로 나오면서 while문에 머물러 push 되기 전에 pop이 진행된다.

즉 1이 pop 되고 k -1 된 후에도 while문에 있어서 또 다시 4가 pop되고 그 이후에 7이 들어가게 된다.

 

stack = ["7"] / 7 비교 / k = 2

-> 동일하니 대체되지 않고 그대로 push한다.

 

stack = ["7", "7"] / 2 비교 / k = 2

-> 7이 더 크니 대체되지 않고 그대로 push한다.

 

stack = ["7", "7", "2"] / 5 비교 / k = 2

-> 5가 더 크니 pop되고 k -1 한 후 push한다.

 

stack = ["7", "7", "5"] / 2 비교 / k = 1

-> 5가 더 크니 대체되지 않고 그대로 push한다.

 

stack = ["7", "7", "5", "2"] / 8 비교 / k = 1

-> 8이 더 크니 pop되고 k -1 한 후 push한다.

 

stack = ["7", "7", "5", "8"] / k = 0

-> 이후 다른 값들은 그대로 push한다.

 

최종적으로 stack = ["7", "7", "5", "8", "4", "1"].join 하면 775841이 출력된다.

 

function solution(number, k) {
  const arr = number.split("");
  const stack = [];

  for (let i = 0; i < arr.length; i++) {
    while (k > 0 && stack[stack.length - 1] < arr[i]) {
      stack.pop();
      k--;
    }
    stack.push(arr[i]);
  }
  return stack.join("");
}

그런데2 테스트 케이스 12번에서 오류가 났다.

반례로 "4321", 1을 얻어 해보니 432가 나와야 하는데 while문 조건이 충족되지 않아 계속 push가 이뤄져 4321이 나오는 것이었다.



앞에서부터 큰 수가 들어왔으니 뒤를 잘라야 한다고 생각했다.

따라서 stack.length가 arr.length - k 보다 크다면 잘라줘야 한다. (4321에서 1개 삭제하면 432로 3자리가 된다.)

 

0번 인덱스부터 stack.length - k (4-1 = 3 앞, 즉 2번까지 나와야 한다.)까지 잘라주면 된다.

 

function solution(number, k) {
  const arr = number.split("");
  const stack = [];

  for (let i = 0; i < arr.length; i++) {
    while (k > 0 && stack[stack.length - 1] < arr[i]) {
      stack.pop();
      k--;
      console.log(stack);
    }
    stack.push(arr[i]);
  }
  if (stack.length > arr.length - k) {
    return stack.slice(0, stack.length - k).join("");
  }
  return stack.join("");
}

 

while문에 덕지덕지 조건 붙이는 부분에서 구현이 어려웠다...