Remove K Digits [leetcode]

문제링크

 

문제 풀이

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

첫번째 풀이

처음에는 앞 숫자와 뒤 숫자를 비교해서 뒤 숫자가 크면 해당 숫자를 지우는 로직인줄 알았다.

그럼 위 예시로 보면

1 : “4” 32219→ 4가 크므로 4를 지운다 ⇒ 132219 (k =2)

1 : “3” 2219→ 3이 크므로 3을 지운다 ⇒ 12219 (k=1)

1 : “2” 219→ 2가 크므로 2를 지운다 ⇒ 1219 (k=0 이므로 종료)

그럼 정답으로 1219 이므로 쉽게 푼줄 알았다.

 

하지만 반례로

Input: num = "12345", k = 2
Output: "123"

위 반례가 있다.

1 : 2 → 2가 크므로 2를 지운다 ⇒ 1345 (k=1)

1 : 3 → 3이 크므로 3을 지운다 ⇒ 145 (k=0 이므로 종료)

정답인 123 과 다르다...

 

 

2번째 풀이

그렇다면 앞 숫자와 뒤 숫자를 비교했을때 앞 숫자가 크면 지우게끔 만들고,

12345 같이 앞숫자가 계속 작았다면! (k가 지워진게 없을테니)

남은 만큼 뒤에서 부터 지우면 되지 않을까?

그럼 12345 의 경우에는 k=2인 채로 loop 가 끝날테니 loop 끝나고 뒤에 두자리를 지우면 123이 나올터였다.

 

 

하지만 반례로...

Input: num = "1234567890", k = 9
Output: "0"

k가 지워지는 유일한 구간은. 9 : 0 비교시 9를 지울때 뿐이다. (k=8)

그럼 123456780 에서 뒤에서 부터 지울테니 답은 1이 나오게 된다...

 

 

3번째 풀이

자 그렇다면 앞 숫자와 뒤 숫자를 비교할때 뒤 숫자가 작다면 계속 비교해서 지우면 안될까?

12345678 9 : 0 이면 9 지우고 (k=8)

1234567 8 : 0 이면 8 지우고

123456 7 : 0 이면 7 지우고

12345 6 : 0 이면 6 지우고

.

.

이런식으로 한번 비교로 끝나는게 아니라 0 자리에 왔을때 계속해서 지워나가면 어떨까?

코드로 보자 (list의 변수 이름을 stack으로 한건 마지막 자리를 비교하고 넣고 빼는거 같아서...)

if stack[-1] > n: # 9 > 0 이면
  while len(stack) > 0 and k > 0: # 스택이 비어있지 않고, K값이 0보다 클때
      last = stack.pop() # 마지막 숫자 pop
      if last > n: # 마지막 숫자가 0보다 크기 때문에
          k -= 1 # k-1 해준다 (pop으로 이미 스택에서는 빠졌다)
      else: # 마지막 숫자가 크다면
          stack.append(last) #pop했던 숫자를 원복해주고 루프를 빠져나온다.
          break 
  stack.append(n) # 못넣었던 숫자를 넣어준다.

 

이 작업을 통해서도 K가 0이 되지 않았다면 위 2번째 풀이 에서 진행했던 마지막 숫자들을 지워줄 필요가 있다.

(앞 숫자보다 뒤 숫자가 더 크기 때문에 위 로직을 타지 않는다.)

if k != 0:
  while k != 0:
      last = stack.pop() # 마지막 숫자 
      prev = stack.pop() # 마지막 이전 숫자 
      if last < prev: # 둘을 비교해서 작은 숫자만 스택에 넣어준다.
          stack.append(last)
      else:
          stack.append(prev)
      k -= 1 # 해당 작업시 마다 k값은 하나씩 사라짐

 

또 주의 점이 있다.

“01” 은 “1” 로 변경되어야 한다. (숫자의 맨앞은 0이 오면 안되므로)

first = stack[0]
while first == "0":
    stack.pop(0)
    if len(stack) > 0:
        first = stack[0]
    else:
        break

 

위 작업이 끝났을때 스택이 비어 있다면 “0” 으로 치환하라고 문제에 써 있으므로

result = ""
if len(stack) == 0:
    return "0"
else:
    result = "".join(stack)

결과는

이번 코드는 내가 봐도 좀 더럽다...

전체코드

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if len(num) == k:
            return "0"
        
        stack = []
        for n in num:
            if len(stack) == 0:
                stack.append(n)
            else:
                if k == 0:
                    stack.append(n)
                else:
                    if stack[-1] > n:
                        while len(stack) > 0 and k > 0:
                            last = stack.pop()
                            if last > n:
                                k -= 1
                            else:
                                stack.append(last)
                                break
                        stack.append(n)
                    else:
                        stack.append(n)
        
        if k != 0:
            while k != 0:
                last = stack.pop()
                prev = stack.pop()
                if last < prev:
                    stack.append(last)
                else:
                    stack.append(prev)
                k -= 1
                
        first = stack[0]
        while first == "0":
            stack.pop(0)
            if len(stack) > 0:
                first = stack[0]
            else:
                break
        
        result = ""
        if len(stack) == 0:
            return "0"
        else:
            result = "".join(stack)
        
        return result