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

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

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

import sys
def solution(number, k):
    n = len(number)-k
    ans = ''
    
    while n > 0:
        if n == len(number):
            ans += number
            break
        sub = number[:-n+1] if n >=2 else number
        m = -1
        idx = sys.maxsize
        for i in range(len(sub)):    
            if sub[i]=='9':
                idx = i
                m = 9
                break
            if m < int(sub[i]):
                idx = i
                m = int(sub[i])
                
            
        ans += str(m)
        number= number[idx+1:]
        n -= 1
    return ans

아이디어 정리:

n = 택할 숫자의 개수

만약 n=4일때 뒤에 3개를 뺀 나머지 중 가장 큰 값을 찾아냄 / 그 값과 인덱스를 찾아서 값은 ans에 추가하고 인덱스는 이 인덱스를 이용해서 number를 그 최댓값 다음부터로 잘라낸다.

 

시간이 굉장히 오래 소요 되었는데

첫번째 이유 - while 문 중단하는 구문에서 break가 아닌 return을 쓰는 바람에 계속 원인을 못찾고 헤맴

두번재 이유 - 가장 큰 값과 인덱스를 찾을 때 max함수와 index함수를 사용했었는데 시간초과가 계속 뜸.

그래서 직접 for문으로 최댓값을 찾다가 9가 나오면 즉시 중단하는 방식의 최적화를 사용하였다. 그래서 결국 시간을 맞출 수 있었다.

 

결론 - 사소한 실수 줄이고 최적화에 좀 더 신경쓰자