[프로그래머스] 큰 수 만들기 (Level 2) (파이썬 python)

 

문제 링크

 

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

프로그래머스

 

 

문제 풀이

 

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

 

combinations를 활용해서 최대를 구하는 방식을 생각해보았지만

순서도 엉키고 시간도 초과된다.

stack을 활용해서 시간적으로 효율적인 코드를 작성할 수 있었다.

 

주어진 number에서 앞에서부터 숫자를 하나씩 확인한다.

 

1. stack(변수 이름 answer)이 존재하며, 2. 삭제해야 할 개수가 채워지지 않았고

3. 현재 숫자가 stack의 맨 뒷 숫자보다 클 경우

n보다 작은 answer의 원소들을 하나씩 삭제해준다.

이때 k를 1씩 감소시켜준다 (앞 숫자들 중 작은 숫자들이 삭제되고 있는 것이므로)

현재 원소보다 작은 숫자들이 모두 사라졌다면, answer에 현재 원소를 추가해준다.

 

이런식으로 반복하게 되면, answer에는 앞에서부터 큰 숫자를 채워주기 때문에

최종적으로 가장 큰 수가 된다.

 

만약 answer의 크기가 k를 잘라낸 길이보다 클 경우

원하는 길이 (원래 숫자의 길이 - k) 만큼 슬라이싱하여 반환해준다.

 

 

느낀 점

 

아이디어를 떠올리는 것 자체도 쉽지 않다...

막상 코드를 작성해보면 너무 간단한데 조건 하나하나를 생각하는게 어려운 것 같다