[프로그래머스] 큰 수 만들기 (Lv2) / 그리디, stack 활용

문제요약

나의 코드 및 설명 (백트래킹) - 당연히 시간초과..

• number의 각 자리를 방문하면서 temp_list 라는 임시 테이블에 담는다. 
  temp_list의 길이가 len(num_list)-k 가 된다면, result 리스트에 숫자로 변환한 값을 저장한다.
• result에 저장된 값중 가장 큰 값을 문자열 형태로 변환 후 출력한다.

v = []

def solution(number, k):
    answer = ''
    num_list = list(map(int, str(number)))
    result = []
    
    def dfs(count, start, temp_list):
        if len(temp_list) == len(num_list) - k:
            result.append(int("".join(map(str, temp_list))))
            return
        if count == len(num_list) - k:
            return
        for i in range(start, len(num_list)):
            if i not in v:
                v.append(i)
                dfs(count+1, i+1, temp_list+[num_list[i]])
                v.pop()
            
    dfs(0,0,[])
    answer = str(max(result))
    
    return answer

다른 코드 및 설명 (스택 활용)

• 숫자를 넣을 stack 리스트를 생성한다.
• number의 각 자리를 방문하면서, 
  만약 stack 안에 무언가라도 존재하고, k의 값이 1 이상(남아있는 제거 할수 있는 횟수가 1이상)이고, 방문한 number의 자리가 stack에 저장된 마지막 값보다 크다면, stack에 저장된 마지막 값을 제거하고, k의 값을 1만큼 감소시킨다.
• 무조건 stack에 방문한 number의 자리를 저장한다.
• answer = "".join(map(str, stack[:len(number)-k])) :
  예를들어 number = "987654321", k=4 일 경우, 정답으로 출력되어야 할 값은 "98765"일 것이다.
  number의 각 자리의 숫자들은 내림차순이고, 이 경우에는 while문의 수행 조건에 해당하지 않기 때문에, stack에 저장된 값이 pop()되거나, k의 값이 감소되지 않는다.
  따라서, stack[:len(number)-k] 를 통해 k>0일 때를 대비해서 스택을 잘라준다. 

def solution(number, k):
    answer = ''
    stack = []
    for i in number:
        while stack and k>0 and i>stack[-1]:
            stack.pop()
            k-=1
        stack.append(i)
    answer = "".join(map(str, stack[:len(number)-k]))
            
    return answer

피드백

제한 조건에 number의 범위가 최대 백만자리이므로 백트래킹으로 구현하면 당연히 시간초과가 발생할 것을 알고 있었다.. 
처음엔 스택으로 풀어보려다가 어떻게 구현해야할지 막막했고, 실패했다. 여러 번 시도 끝에 구현에 실패하느니 백트래킹 풀고 몇 개의 테스트케이스라도 맞자라는 생각으로 백트래킹으로 풀었다. 예제 테스트케이스는 모두 맞았으나 역시나 나머지 테스트케이스에서는 시간초과가 발생했다.

스택을 활용한 문제풀이를 보고 경악했다.. 어떻게 이 문제를 이렇게 간단하게 구현할 수 있을까 많이 좌절했다. 백준 문제를 많이 풀면서 스택을 활용하는 것도 연습 했었기 때문에, 간단히 스택을 활용하는 것은 자신있었는데 새로운 배움을 맞이한 느낌이었다. 
여러 번 코드를 분석한 끝에 코드를 이해할 수 있었고, 잘 흡수해서 내 것으로 만들어야겠다.