[프로그래머스 Lv.2] 큰 수 만들기 (파이썬 풀이)

문제 링크

프로그래머스

 

[풀이]

* 이 문제는 시간 복잡도를 최소화해야 함.

* 탐욕법(Greedy) 유형의 문제라는 것이 힌트.

* combinations나 max 함수로는 제한 시간에 맞추기 어려움.

 

1. 만들고자하는 가장 큰 수의 앞자리부터 순서대로 찾기 위한 범위를 매번 설정해야 한다.
2. 찾을 범위 시작 위치 인덱스는 0, 끝 위치 인덱스는 (number의 총 길이 - 만들고자하는 수의 총 길이)로 초기화 한다.
3. 찾을 범위 끝 위치 인덱스+1 로 범위를 갱신하고 현재 범위 내에서 최댓값을 찾아 정답이 될 문자열 변수에 추가한다.
4. 찾을 범위 시작 위치 인덱스를 찾은 최댓값의 인덱스+1 부터로 범위를 갱신한다.
5. 정답이 될 문자열 변수의 길이가 만들고자 하는 수의 총 길이가 될 때까지 3~4번을 반복한다.

* 3번을 수행할 때는 max 함수가 아닌 반복문으로 9부터 내림차순으로 찾고 찾은 즉시 반복문을 종료하여 시간을 단축한다.

 

[코드]

def solution(number, k):
    answer = ''
    fi, bi = 0, len(number)-(len(number)-k)
    while len(answer) < len(number)-k:
        bi += 1
        tmp = number[fi:bi]
        for i in range(9, -1, -1):
            if str(i) in tmp:
                max_tmp = str(i)
                break
        answer += max_tmp
        fi += tmp.index(max_tmp) + 1
    return answer