lv2 큰 수 만들기

문제 링크

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

 

문제 설명

어떤 숫자에서 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)의 최적성(optimality)에 영향을 주지 않음

솔루션

주어진 숫자(number)에서 왼쪽부터 하나씩 꺼내어 모으되,

1. 이때, 이미 모아둔 것 중 지금 등장하는 것보다 작은 것들은 빼낸다.
2. 단, 이때 유효한 숫자를 모두 소진할 때 까지만 뺀다.
3. 아직 뺄 개수(k)를 채우지 못한 경우 뒤에서 부터 남은 자리수만큼 뺀다.

코드

sol1) 스택을 이용한 풀이

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0: # 파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:   # while문을 다 돌았는데 k가 0이 아니면 뒤에서부터 pop한다
        stack = stack[:-k]
    return ''.join(stack)

sol2) 스택을 이용한 풀이2

def solution(number, k):
    stack = []
    for x in number:
        while stack and k >0 and stack[-1] < x:  # 파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            stack.pop()
            k -= 1
        stack.append(x) # 맨 처음에는 stack이 비어있으므로 while문 돌지 않고 x부터 append함
    if k!=0:
        stack = stack[:-k]
    res = ''.join(map(str, stack))  
    return res

sol3) 스택과 큐를 이용한 풀이

from collections import deque
def solution(number, k):
    cnt = 0
    q= deque(number)
    sol = []
    sol.append(q.popleft()) #number의 첫글자를 stack에 넣고 시작
    while q:
        x = q.popleft()
        while sol and x > sol[-1] and cnt !=k:  # 스택의 맨위 글자와 큐의 왼쪽 첫번째 글자를 비교해서 스택의 맨위 글자가 더 작으면 크거나 같아 질때까지 스택의 맨 위 글자를 pop한다. 이 때 pop을하다 pop의 숫자가 k가 되면 멈춘다
                                                # 또한, 스택이 비어있으면 pop을 못하므로 비게 되면 멈춘다
                                                #  파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            sol.pop()
            cnt +=1 
        sol.append(x)                           
        while (not q) and (cnt != k) :         #만약 q의 원소를 모두 썼는데 cnt에 도달 못했으면 도달할때까지 뒤에서부터 빼냄
            sol.pop()
            cnt +=1
    return ''.join(sol)

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges