프로그래머스 큰 수 만들기.py

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

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

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

 

풀이 방법 : 간단하게 앞에 있는 숫자(큰 자릿수)가 뒤에 있는 숫자(작은 자릿수)보다 작으면 앞에 있는 숫자를 지워주는 방식으로 풀었습니다. k개 만큼을 이러한 방식으로 지운 후 남은 number는 큰수가 앞, 작은수가 뒤로 정렬이 되어 있는 상태 이므로 뒤에서 부터 k개 만큼 줄인 후 return해 주면 됩니다.

 

# 나의 풀이

def solution(number, k):
    answer = ''
    stack = []
    i = 0
    while True:
        if i == len(number):
            break
        if k == 0 or len(stack) == 0:
            stack.append(number[i])
        elif stack[-1] <  number[i]:
            stack.pop()
            i -= 1
            k -= 1
        else:
            stack.append(number[i])
        i += 1
    if k == 0:
        print(1)
        return "".join(stack)
    # 정렬이 되어 있는것을 생각하지 못하고 작은 수 부터 차례로 지워줬습니다.
    while True:
        for i in range(0, 10):
            for j in range(len(stack)):
                if int(stack[j]) == i:
                    stack[j] = ""
                    k -= 1
                    if k == 0:
                        return "".join(stack)

 

# 좋은 풀이 

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

비슷한 방식이지만 if, else문이 훨씬 적고 깔끔하게 풀이 되어 있다.