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

문제 설명

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

---

나의 답

def solution(number, k):

    s = []
    from collections import deque
    number = deque(list(number))
    
    curr = number.popleft() 
    s.append(curr)
    while number:
        curr = number.popleft()
        while s and curr> s[-1] and k>0:
            s.pop(-1)
            k-=1
        s.append(curr)

    if k>0:
        s = s[:-k]
            
    return ''.join(s)

• 레벨이 2밖에 안되는데 엄청 오래 걸린 문제입니다. 
• 시행착오 정리
  1. 숫자를 미리 자르고 큰 숫자로 시작하려던 시도
     • 처음엔 number[:k]에서 가장 큰 수를 먼저 골라서, 그 앞까지 날리고 시작하면 되지 않을까? 라고 생각함.

     • def solution(number, k):
           part_number = max(list(map(int, number[:k])))
           if part_number >= int(number[k]):
               for idx,i in enumerate(number):
                   if i != str(part_number):
                       k-=1
                   else:
                       number = number[idx:]
                       break
           # print(number)
           s = []
           from collections import deque
           number = deque(list(number))
           
           curr = number.popleft() # 9
           s.append(curr)
           while number: # 24
               curr = number.popleft() # number 24
               while s and curr> s[-1] and k>0:
                   s.pop(-1)
                   k-=1
               s.append(curr)
       
           if k>0:
               s = s[:-k]
                   
           return ''.join(s)

     • 실제로 그런 코드를 앞에 넣어서 함. 이렇게 해도 정답이 맞긴한데 코드가 길어지고 저 과정이 없어도 되는 문제였음 
  2. 스택 알고리즘을 활용할 생각을 못 함
     • "4177252841" 이라는 문자열이 있을 때, 앞에서부터 하나씩 비교하면서 다음 오는 수가 현재 수보다 크면 현재 수를 제거하는 방식으로 어떤 수를 제거할지 결정하는 방법론을 생각함
       • ex. 4177252841에서 k가 4일때
         • 4와 1을 비교하면 1이 4보다 작으므로 통과
         • 1과 7을 비교 → 1< 7 이므로 1을 제거 → 477252841
         • 다시 앞에서부터 4와 7을 비교 → 4<7 이므로 4 제거 → 77252841
         • 7과 7 비교 → 같으니까 패스
         • 7과 2 비교 →7>2 이므로 패스
         • 2와 5 비교 → 2<5 이므로 2 제거 →7752841
         • 제거한 2 앞에 있던 수들 (7 7) 과 5 비교했을때 7이 더 크므로 패스
         • 5와 2 비교 → 5>2 이므로 패스
         • 2와 8 비교 → 2<8 이므로 2 제거 →775841
         • k=4, 즉 4개 수 제거했으므로 답은 775841
       • 이런 과정을 생각했으나 구현까지 하는데에 실패함
       • 스택을 사용해서 앞에서부터 수를 하나씩 stack에 쌓아주는데 쌓기전에 stack 위에 수와 비교해서 넣으려는 수가 더 크면 스택에 있는 수를 제거하는 방식으로 코드를 짜면 됨
     • while 문에서 while s and curr> s[-1] ... 이 있는데 이렇게 짜주면 s 가 빈 스택일때 while s에서 false가 되므로 뒤에 s[-1]이 실행되지 않음 -> 인덱스 에러 해결 가능
  3. 마지막에 k가 남았을 때 제거하지 않음
     • 숫자가 내림차순인 경우(예: "9876543210")
       → 한 번도 pop()이 일어나지 않음 → k 그대로 남음 → 뒤에서 k만큼 제거 필요!

     • if k > 0:
           s = s[:-k]

     • 이 줄이 없으면 마지막 테스트 케이스에서 실패를 했다