[프로그래머스] 2021 카카오 공채 - 큰 수 만들기 (파이썬)

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

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

문제설명

이번 문제는 특정 숫자와 상수가 주어지고, 숫자에서 상수 만큼 숫자를 제거해 가장 큰 수를 출력하는 문제이고, 특정 숫자와 상수의 크기가 작지 않아 계속 시간초과 때문에 애먹었던 문제였다.

 

풀이

내 풀이는 맨 뒤에서 최종 answer의 길이 만큼 먼저 잘라낸 이후 answer의 첫번째 값과 num의 마지막 값을 비교하여, answer[0]의 값이 클경우 num[-1]를 버리고, answer[0]값이 작을 경우 answer에서 숫자 하나를 지우고 num[-1]값을 answer 맨 앞으로 넣어주는 방법으로 진행하였다. 

 

def solution(number, k):
    answer=list(number[k:])
    num=list(number[:k])
    l=len(answer)
    check = [i for i in range(l-1) if answer[i]<answer[i+1]]
    if l==1: return max(number)
    while num and answer: #k=l 같거나 K개 만큼 빼는동안 
#         print(num,answer,check)
        t=num.pop(-1)
        if t>=answer[0]:
            if check:
                c=check.pop(0)
                answer.pop(c)
                answer.insert(0,t)
                if c == 0 and t<answer[1]: check.insert(0,0)
                if c !=0 and answer[c]<answer[c+1]: check.insert(0,c)
            else : 
                answer.pop(-1)
                answer.insert(0,t)
#         print("--------------------------------------------------")
    return "".join(answer)

 

다른 사람 풀이

이 분은 처음부터 끝까지 크기 비교만으로 진행을 하여 훨씬 더 효율적으로 정리하였다.  K!=0 이 부분은 더 이상 크기비교로 지워지지 않은 부분, 즉 값을 앞뒤로 비교했을때 커지는 값이 없지만, 제거해야할 숫자가 남았을 경우 처리하기 위한 부분이다.

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)

느낀점

answer에서 계속 크기 비교하고 지우는 작업이 있어서 시간이 훨씬 오래 걸렸다. 내 논리를 좀 더 정확하게 다지고 정리하는 연습이 필요할 것 같다. answer했던 작업들만으로도 충분히 해결 할 수 있었던 문제였는데, 문제를 보고 정리하는 연습이 필요할것 같다. 

첫 번째 코드 : 420.86ms / 두 번째 코드 : 16.67ms