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

문제

• 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기
• 2 <= number <= 1,000,000

 

풀이 1

• 문자열에서 뒷 숫자보다 작은 숫자가 앞에 있으면 제거한다.
  • "1231234" , k=3 예시
    • 1은 2보다 작으므로 제거
    • 2는 3보다 작으므로 제거
    • 3은 1보다 크므로 보류
    • 1은 2보다 작으므로 제거
• 문자열을 뒤집어 pop 연산이 좀 더 빠르게 이뤄지게 한다.

 

def solution(number, k):

    n = len(number)
    number = list(map(str, number))[::-1]   # 문자열 뒤집기

    # k개 제거
    for _ in range(k) :
        # 문자열 뒤부터 확인해 작은 숫자 제거
        for i in range(n-1, -1, -1) :       
            if number[i] < number[i-1] :
                number.pop(i)
                n -= 1
                break
            
    return ''.join(number[::-1])

 

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.06ms, 10.1MB)
테스트 4 〉	통과 (0.22ms, 10.3MB)
테스트 5 〉	통과 (1.37ms, 10.1MB)
테스트 6 〉	통과 (446.80ms, 10.2MB)
테스트 7 〉	통과 (943.03ms, 11.1MB)
테스트 8 〉	통과 (9293.99ms, 11.7MB)
테스트 9 〉	통과 (27.84ms, 15.1MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (0.01ms, 10.1MB)
테스트 12 〉	통과 (0.01ms, 10.3MB)

 

풀이2

• 9가 나오면 더 큰 숫자가 없으므로 탐색할 필요가 없다. 탐색의 개수를 줄이기 위해 탐색의 시점을 9 이후로 정해준다. 

def solution(number, k):

    n = len(number)
    number = list(map(str, number))[::-1]   # 문자열 뒤집기

    # k개 제거
    for _ in range(k) :
        # 문자열 뒤부터 확인해 작은 숫자 제거
        for i in range(n-1, -1, -1) :       
            if number[i] < number[i-1] :
                number.pop(i)
                n -= 1
                break
            if number[i] == '9' :	# 9가 나오면 더 큰 숫자는 없으므로 기준점 변경
                n = i
        
    return ''.join(number[::-1])

 

References

• 프로그래머스 고득점Kit 그리디