문제링크

https://leetcode.com/problems/remove-k-digits/

input & output

Example 1

Input: num = "1432219", k = 3
Output: "1219"

Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2

Input: num = "10200", k = 1
Output: "200"

Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3

Input: num = "10", k = 2
Output: "0"

Explanation: Remove all the digits from the number and it is left with nothing which is 0.

문제 설명

주어진 num에서 k개 만큼의 숫자를 제거했을때 나올수 있는 가장 작은 num을 리턴하면 된다.
예를들어 num = "1432219" , k=3 의 경우 4,3,2 세 숫자를 제거한 "1219" 가 가장 작은 숫자가 된다.

---

Approach #1

스택 만들어서 push한다. 이때 제일 끝값이 현재 들어올값보다 크면 pop해준다.
pop해줄때 k-- 해주면서. 
k===0 되면 푸쉬하지 않은 나머지값을 마저 넣어준다.

Solution #1

var removeKdigits = function(num, k) {
  //edge case
  if(num.length === k) return "0";
  
  const stack = [];
  for(let i=0; i<num.length; i++){
      while(k>0 && stack[stack.length-1] > num[i]){
          stack.pop();
          k--;
      }
      stack.push(num[i]);
  }
  
  // ex. num = "112" k=1
  while(k>0){
      stack.pop();
      k--;
  }
  
  while(stack.length && stack[0]==="0"){
      stack.shift();
  }
      
  return stack.length ? stack.join("") : "0";
};

N: num.length
k = k

Time Complexity

O(N*k)

스택에 값 push해주는 for문에서 O(N*k).

stack의 앞자리가 0일때 shift해주는 while문에서 worst case("00000~")일때 아무리 커봐야 O(N)보다 작을것.

stack값들 join해줄때 O(N-k).(<-join 시간복잡도 O(N)맞나? ... 찾아봐야겠다. 정확하지 않기때문에 이 포스팅에서는 제외하고 생각하기로 함.)

=> O(NK) + O(N)
=> 대략 O(Nk)

Space Complexity

O(N-k)

stack의 최대 길이가 N-k이기 때문에 공간복잡도는 O(N-k).

Review

1. 이 문제는 리뷰하라고 하면 할말이 정말 많다... 일단 첫번째 시도했던 로직에서 테스트케이스 4개 남기고 실패했기 때문... 내기준에서 나름 괜찮은 로직이라 생각했는데 ㅎ.ㅎ... 실패한 코드지만 아까우니까 아래에 기록해 둘 예정.

var removeKdigits = function(num, k) {
  if(num.length === k) return "0";
  
  let minCutNum = Number.MAX_VALUE;
  let minCutNumStr = "";
  
  while(k>0) {
    for(let i=0; i< num.length; i++) {
      let cutNumStr = num.slice(0, i)+num.slice(i+1);
      let cutNum = Number(cutNumStr);
      
      if(minCutNum > cutNum){
        minCutNum = cutNum; 
        minCutNumStr = cutNumStr;    
      }
    }
    num = minCutNumStr; 
    k--;
  }
  
  while(minCutNumStr[0]==="0"){
    if(minCutNumStr[0]!=="0") break;
    else minCutNumStr = minCutNumStr.slice(1);
  }
  return minCutNumStr ? minCutNumStr : "0";

};

2. 위 코드의 로직은.. for문 안에서 주어진 cutNumStr에서 한자리씩을 빼보며(ex. "1234"라면 "234", "134", "124", "234" 다 비교함) 가장 작은 스트링을 num으로 넘겨주며(앞의 예시에서 제일 작은 값인 "124"를 num으로 넘겨주며 또 한자리씩 빼봄 "24", "14", "34".. 요렇게) while문을 반복하는.. 그런 형태이다.

3. 통과하지 못한 테스트케이스는 num이 정말 어어어어엄청 긴 문자열이었는데. 타임리밋도 아니고 wrong answer? 답이 자꾸 "0"으로 뜨길래 설마 minCutNumStr이 null로 들어가나? 싶어서 vscode에서 출력해보니 진짜 널값이었다. 왜?????? 하고 제일 처음 i가 0일때 cutNum을 출력해보니 세상에.. Infinity???
   num.length의 최대가 10^5 이니까.... 자릿수가 10000만개..... 라는 소리니까.... 그걸 숫자로 바꾸면 Infinity가 나올수밖에 없겠구나. 이 로직은 잘못되었구나. 이틀 내내 붙잡고 있다가 Infinity를 보는 순간 다른 로직을 생각해야겠구나. 던져버렸다. ㅎ.ㅎ...하하 ㅠㅠ

4. 새롭게 생각한 풀이는 힌트를 살짝 참고했다. 바로 Stack !

5. 스택에 num[i]값을 push해주는데, 제일 끝에 들어온 값과 현재 들어올 값을 비교해서 제일 끝에 들어온 값이 더 크면 pop해주며 넣어주는 형식. k번 pop()을 해주면 내가 뺄 k digits는 다 remove 된것이니까, 나머지 num[i]를 push해주는....

6. num="112" k=1 이라는 테스트케이스 통과를 못해서 두번째 while문을 추가해주었다. 두번째 while문은 마지막자리까지 push해 줬는데 k개만큼을 못빼준 경우.(ex. 22222233 k=2 라면 답은 22222가 나와야하는데, 첫번째 for문에서는 끝값이 클때만 pop해주기 때문에 2222233이 스택에 쌓인다.) 다시 k번 pop해주어 올바른 답이 나오도록 했다.

7. 세번째 while문은 "00001" 일때 "1"로만 리턴하기 위해 맨 앞이 0이면 shift해주는 코드이다.

8. 마지막 return 해주는 부분에서는 만약 "00000"이면 세번째 while문에서 0을 전부 shift해주어 stack이 비어있게 되는데, 이런 경우는 "0"을 리턴해줘야 하기 때문에 삼항연산자로 stack의 상태에 따라 return을 달리하도록 코드를 작성해줬다.

TIL

1. 자바스크립트에서 MAX_VALUE의 값은 약 1.79e+308, 즉 2^1024이다.
   MAX_VALUE 보다 큰 값은 Infinity로 표현된다.

2. 배열의 element들을 합쳐 문자열로 만들고 싶을때는 arr.join('') 를 사용하면 된다.

3. 문자열에서 i번째 문자 1개만 삭제한 문자열을 만들고 싶은 경우, str.slice(0,i)+str.slice(i+1) 해주면 된다.

4. 문자열에서 맨앞 문자 1개만 삭제된 문자열을 만들고 싶은경우, str.slice(1) 해주면 된다. (1번째 인덱스~ 마지막 인덱스 문자열을 리턴하기 때문에 0번인덱스를 삭제한 꼴이 된다.)

---

Approach #2

/*
Input: num = "1432219", k = 3
Output: "1219"

  0 1 2 3 4 5 6
  i,4,3,i,2,i,9
i             ^
j             ^

min = [9,6]
result=[1,2,1]
*/

Solution #2

var removeKdigits = function(num, k) {
  //edge case
  if(num.length === k) return "0";
  
  let res = [];
  let numArr = num.split('');
  for(let i=k; i<numArr.length; i++){
      let min = [numArr[i], i];
      for(let j=i; j>=0; j--){
          if(numArr[j]===Infinity) break;
          if(min[0] >= numArr[j]) {
              min[0] = numArr[j];
              min[1] = j;
          }
      }
      res.push(min[0]);
      numArr[min[1]]=Infinity;
  }
  
  while(res && res[0]==="0"){
      res.shift();
  }
  
  return res.length ? res.join('') : "0";
};

N: num.length
k = k

Time Complexity

O(N-k)*O(N)+O(N)

첫번째 i for문에서 O(N-k), j for문에서 worst일때("00000~") 대략 O(N)만큼.

stack의 앞자리가 0일때 shift해주는 while문에서 worst case("00000~")일때 아무리 커봐야 O(N)보다 작을것.

stack값들 join해줄때 O(N-k).(<-join 시간복잡도 O(N)맞나? ... 찾아봐야겠다. 정확하지 않기때문에 이 포스팅에서는 제외하고 생각하기로 함.)

=> O(N-k)*O(N)+O(N)

Space Complexity

O(N-K)

stack의 최대 길이가 N-k이기 때문에 공간복잡도는 O(N-k).

Review

1. 문자열을 자르거나 삭제할때 O(N)만큼의 시간복잡도가 소요되기 때문에 split 함수를 이용해 배열로 바꿔주었다.

2. min배열은 0번째 원소로 문자를, 1번째 원소로 그 문자의 인덱스를 갖고있는 배열이다.

TIL

1. 문자열의 문자들을 쪼개 배열에 넣고싶을때는 arr = str.split(''); 기억하자!

---