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

문제 확인

프로그래머스

 

나의 풀이

DFS를 활용한 풀이 : 시간 초과

문자 조합을 구성하기 위해서 DFS를 활용했다.

조합 구성 시, 순서를 유지하기 위해서 start 변수를 도입해 탐색 범위를 제한했다. 

• 시간 초과가 발생했다. 
• 풀이의 시간 복잡도는 ${n \choose k}$ 인데, n과 k가 최대 100만 까지 가능하기 때문이다.

• DFS 함수의 시간 복잡도

T(dfs) = (n-k) choose (k-1) + (n-k+1) choose (k-1) + ... + n choose (k-1)
       = (n+1) choose k - (n-k) choose k
       = O(n choose k)

import sys

sys.setrecursionlimit(10 ** 6)

uniq_num = set()

def dfs(number, cnt, k, start):
    if cnt == k:
        num = "".join([number[idx] for idx, check in enumerate(is_blank) if check == 0])
        uniq_num.add(int(num))
        return
    for i in range(start, len(number)):
        if not is_blank[i]:
            # 제외할 숫자로 선택
            is_blank[i] = 1
            dfs(number, cnt + 1, k, i)
            is_blank[i] = 0

def solution(number, k):
    global is_blank
    is_blank = [0] * len(number)
    dfs(number, 0, k, 0)
    return str(max(uniq_num))

 

참고하여 푼 풀이

Stack(스택)을 활용한 Greedy(그리디)

가장 큰 수가 되려면 결국, 맨 앞자리의 숫자가 가장 커야 한다.

이를 만족하도록 숫자들을 제거해주면 된다.

 

숫자는 앞자리부터 제거되고, 한번 입력/제거 된 숫자는 다시 활용되지 않는다.

따라서 스택을 활용해 맨 앞자리 부터 차례로 확인하고 바꿔가면, 결국 최대 숫자를 얻을 수 있다.

# 가장 큰 수 : 맨 앞자리가 가장 커야 함
# 한번 제거된 수는 다시 사용되지 않기 때문에 Stack으로 처리할 수 있음
def solution(number, k):
    stack = []
    for n in number:
        # 새로 입력될 숫자가 기존보다 클 경우
        # 변경 진행
        while stack and stack[-1] < n and k > 0:
            stack.pop()
            k -= 1
        stack.append(n)
    # 아직 제거하지 못한 숫자를 뒤에서부터 삭제
    # 제거되지 못한 경우 : 동일한 숫자가 반복된 경우 / K개를 지웠지만 아직 남은 숫자가 있는 경우
    if k > 0:
        stack = stack[:-k]
    return "".join(stack)

프로그래머스 풀기 - 큰 수 만들기