[Python] 프로그래머스 Lv2_큰 수 만들기

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

프로그래머스

 

• 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기
• ex) 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있음
  • 이 중 가장 큰 숫자는 94
• number: 문자열 형식인 숫자
• k: 제거할 수의 개수
• number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return

제한 조건

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

 

"""
입출력 예시)

number = "1924", k = 2 -> "94"
number = "1231234", k = 3 -> "3234"
number = "4177252841", k = 4 -> "775841"
"""

 

 

## 의사코드 ## 

# number에서 k개의 수를 제거했을 때 나올 수 있는 경우 구하기
# combinations(number, len(number)-k))

# combinations로 구한 값들 중 max()를 문자열 형태로 return

 

 

 

첫 번째 시도

 

from itertools import combinations
def solution(number, k):
    numbers = list(map(int, number))
    # number에서 k개의 수를 제거했을 때 만들 수 있는 조합
    combi = list(combinations(numbers, len(number)-k)) 
    max_n = map(str, max(combi))
    return ''.join(max_n)

-> combinations로 조합 구현

-> 추가 테스트 케이스 실패 (시간 초과)

 

 

 

두 번째 시도

 

def solution(number, k):
    numbers = list(number)
    n = len(numbers)
    r = len(number) - k # number에서 k개의 수를 제거한 숫자의 길이
    combi = [] # number에서 k개의 수를 제거했을 때 만들 수 있는 조합
    # DFS 수행
    def dfs(idx, li):
        if len(li) == r:
            combi.append(li[:])
            return 
        for i in range(idx, n):
            dfs(i+1, li+[numbers[i]])
    
    dfs(0, [])

    return ''.join(max(combi))

-> DFS로 조합 구현

-> 추가 테스트 케이스 실패 (시간 초과, 런타임 에러)

 

 

통과한 코드

 

def solution(number, k):
    stack = []
    for num in number:
        if len(stack) == 0:
            stack.append(num)
            continue
        if k > 0: 
            while stack[-1] < num:
                stack.pop() # stack[-1]을 꺼냄
                k -= 1
                if len(stack) == 0 or k <= 0:
                    break 
        stack.append(num)

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

-> stack 활용, 앞자리에 큰 숫자가 와야 전체 수를 크게 만들 수 있다는 점 활용

 

 

• 과정 확인

number = "1231234"
k = 3

"""
k = 3일 때 

num: 1
stack: ['1'] 

num: 2
k: 3
stack: ['1']
stack[-1]: 1
stack[-1](=1) vs num(=2)
stack[-1] < num 인 경우
pop한 stack: []
k: 2
stack.append(num): ['2'] 


num: 3
k: 2
stack: ['2']
stack[-1]: 2
stack[-1](=2) vs num(=3)
stack[-1] < num 인 경우
pop한 stack: []
k: 1
stack.append(num): ['3'] 


num: 1
k: 1
stack: ['3']
stack[-1]: 3
stack[-1](=3) vs num(=1)
k: 1
stack.append(num): ['3', '1'] 


num: 2
k: 1
stack: ['3', '1']
stack[-1]: 1
stack[-1](=1) vs num(=2)
stack[-1] < num 인 경우
pop한 stack: ['3']
k: 0
stack.append(num): ['3', '2'] 


num: 3
k: 0
stack.append(num): ['3', '2', '3'] 


num: 4
k: 0
stack.append(num): ['3', '2', '3', '4'] 


stack: ['3', '2', '3', '4']
stack[:-k]: ['3', '2', '3', '4']

'3234'
"""

 

 

 

다른 풀이

 

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
        
    return ''.join(answer[:len(answer) - k])

 

 

 

참고)

 

https://ckd2806.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EC%BD%94%EB%93%9C%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

[파이썬 python] 순열, 조합 코드로 구현하기

 

https://velog.io/@soo5717/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

Programmers | 큰 수 만들기 - Python