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

문제

https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3

풀이

from itertools import combinations
def solution(number, k):
    lst = list(combinations(range(len(number)), len(number)-k))
    answer = []
    for l in lst :
        answer.append("".join([number[i] for i in l]))
    
    return str(max(answer))

최초 접근한 방법. combinations를 통해 모든 조합을 구한 다음
거기서 최대값을 반환!! 결과는!!!

테스트 1 〉	통과 (0.20ms, 10.1MB)
테스트 2 〉	통과 (3320.16ms, 642MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.01ms, 10.2MB)

그럼 그렇지. 다른 방법으로 접근해보자.

“가장 큰 수를 만드는 쉬운 방법”은 맨 앞자리수에
최대한 큰 수를 배치시키는 것이다.
즉, 앞 쪽에 최대한 큰 수가 올 수 있도록 해야한다.
이걸 신경써서 코드를 작성해봤다.

def solution(number, k):
    number = list(number)
    a = k
    while k > 0 :
        for i in range(len(number)-1) :
            if number[i] < number[i+1] :
                number.pop(i)
                k -= 1
                break
    return "".join(number)

맨 앞자리부터 탐색을 하다가, 바로 다음 값이 지금 값보다 크면
무조건 pop 시키고 다시 첫자리부터 탐색을 진행한다.
이렇게 하면 Greedy 알고리즘 느낌이 살짝 난다.

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.08ms, 10.1MB)
테스트 4 〉	통과 (0.21ms, 10.2MB)
테스트 5 〉	통과 (1.57ms, 10.2MB)
테스트 6 〉	통과 (344.32ms, 10.3MB)
테스트 7 〉	통과 (816.97ms, 10.6MB)
테스트 8 〉	통과 (8557.32ms, 11.1MB)
테스트 9 〉	통과 (52.82ms, 13MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (0.01ms, 10MB)
테스트 12 〉	실패 (시간 초과)

그러나 결과는 여전히 실패였다.
접근 방법은 맞았으나, 문자열의 길이가 길어지면 오버헤드가 너무 큰 것 같다.
저 동작을 축약시킬 방법이 없을까 곰곰히 생각해보니, 스택과 비슷했다.

아하! 스택 반환으로 다시 접근해보자.

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

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.04ms, 10.1MB)
테스트 4 〉	통과 (0.18ms, 10.2MB)
테스트 5 〉	통과 (0.37ms, 10.2MB)
테스트 6 〉	통과 (4.19ms, 10.4MB)
테스트 7 〉	통과 (9.90ms, 10.6MB)
테스트 8 〉	통과 (22.63ms, 10.8MB)
테스트 9 〉	통과 (38.53ms, 13.7MB)
테스트 10 〉	통과 (120.42ms, 13.3MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	실패 (0.00ms, 10.2MB)

훠어어얼씬 빠르고 가볍다. 다만 마지막 케이스에 걸린다.
그런데 테스트케이스 12에서 아예 오답으로 나온다.
걸릴 수 있는 경우에 수가 뭐가 있나 찾아보니, 해당될 만한 부분이 있었다.

number = "1000", k = 2

이 경우 내 코드에서 “1000”이 그대로 출력되게 된다.
반복문을 다 수행하고도 여전히 길이가 안줄이든 경우를 추가하자.

def solution(number, k):
    ok = len(number) - k
    stack = []
    for num in number :
        while len(stack) > 0 and k > 0 and stack[-1] < num :
            stack.pop()
            k -= 1
        stack.append(num)
    
    while len(stack) > ok:
        stack.pop()
    
    return "".join(stack)

완성!! Level2 문제가 맞나 싶을 정도로 시간이 오래 걸렸다.

더 나은 풀이

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

당혹스럽다. 특히 마지막 줄의 경우 충분히 생각해볼 수 있었는데
그저 “드디어 풀었다!” 라는 생각에 반복문을 한 바퀴 더 돌렸다.

다 완성해도 더 다듬을 수 있나 항상 고민하는 자세를 가져야겠다.