큰 수 만들기 (코딩테스트, 프로그래머스, 파이썬)

문제

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

코딩테스트 연습 - 큰 수 만들기

나의 코드(실패)

from itertools import combinations

def solution(number, k):
    answer = 0
    
    for i in list(combinations(range(len(number)),k)):
        tmp=[number[j] for j in range(len(number)) if j not in i]
        answer=max(answer,int(''.join(tmp)))
    
    return str(answer)

combinations을 사용해서 제외시킬 위치들에 대한 조합을 for문을 돌린다 

i가 [0,1]일 때 number 에서 0번째 1번째 위치의 숫자를 제외하겠다는 뜻이다.

그리고 max를 사용해서 기존의 answer와 크기를 비교시켜 최종적으로 가장 큰 값을 선택하도록 한다.

위 코드는 시간초과로 통과하지 못하였다.

 

-----------------------------------------------

나의 코드(성공)

def solution(number, k):
    number = list(number)
    answer = [number[0]]
    count = 0 
    
    for num in number[1:]:
        if answer[-1] >= num or count == k:
            answer.append(num)
        else:
            count = Pop(answer,num,count,k)
        
    return "".join(answer[:len(number)-k])

def Pop(answer,target,count,k):
    while answer[-1] < target and count != k :
        answer.pop()
        count += 1
        if len(answer) == 0 :
            break
            
    answer.append(target)
    return count

시간초과로 통과하지 못하여 검색으로 스택으로 해결한다는 힌트만 듣고 나만의 방식으로 다시 작성해보았다.

하나씩 뽑아서 answer에 자기보다 작은 값이 있다면 생성되는 숫자들은 모두 작은 수가 되니 pop하고 자리를 찾아가는 식으로 문제를 해결하였다.