[Programmers] 큰 수 만들기 - Python

 

1. 문제 설명

 

2. 제한 조건 & 입출력 예

 

 

 

3. 시행착오

3.1. 첫 번째 접근. 단순 정렬

혹시나 하는 마음으로, 그냥 정렬하고 앞부터 끊었다. 당연히 정답이 아니었다.

 

3.2. 두번째 접근. i와 i+1의 비교

i번째 수와 i+1번째 수를 비교하고, i+1 번째 수가 더 크면 i번째 수를 제거하는 방식으로 문제를 풀었다.

이 경우,

4177252841, 4

이렇게 주어졌을 때, 정답이 77841이 나왔다. 즉, 무조건 큰 수를 살린다고 결괏값이 커지는 것은 아니란 이야기다.

 

3.3. 세번째 접근. K를 범위로 하여 Number를 자르고, 그 안에서 최고값 살리기
Step 1과 Step 2로 나누어, 맨 앞자리 숫자를 확정하는 단계가 그 뒤에 숫자들을 정해 가는 단계로 나눠 진행했다. 테스트 10에 대해서 시간 초과가 나버려서 통과하지 못했다. 최고 숫자인 9를 예외로 두어도 결과는 비슷했다. 다른 테스트 케이스를 봐도, 코드가 딱히 효율적이지 않았다. K 범위 내의 리스트 안에서 끊임없이 max() 함수를 썼는데, max() 함수는 시간복잡도가 O(N)이다. 결론은 내 코드가 N*O(N) 복잡도이며, 이 정도론 문제를 풀지 못할 것이란 결론에 도달했다.

 

 

 

 

4. 접근 방식과 코드

위의 방식들은 모두 list 안에서 계속해서 빙빙이를 돌리는 접근이었다. 수가 커질수록 시간복잡도가 기하급수적으로 커지게 되니 효율적인 방식은 아니다. 가장 좋은 방식은 앞에서부터 탐욕법을 '제대로' 활용해서 뺄 거 빼고, 더할 거 더하는 방식으로 수를 만들어 간다. 그 결과가 다음 코드다.

def solution(number, k):
    stack = []
    for num in number : 
        if not stack:
            stack.append(num)
            continue
        while stack[-1] < num and k > 0:
            stack.pop()
            k -= 1
            if not stack or k <= 0:
                break
        stack.append(num)
    stack = stack[:-k] if k > 0 else stack
    return ''.join(list(map(str, stack)))

스택을 활용한다.

앞에서부터 조건을 걸어서, 비어있으면 채우고, 다음에 올 숫자와 비교했을 때 작으면 스택에서 뺀다. 앞의 3.2. 방식과 비슷해보이지만, 스택을 활용했냐 안 했냐에서 이렇게 차이가 발생했다.

 

 

Level 2면 그래도 고민하면 풀리는 경우가 많았는데, 간만에 며칠 붙잡았다.

오랜만에 코테를 했더니 감이 안잡혔나 보다.

당분간은 오래오래 고민하면서 문제를 풀어봐야지.