코딩테스트 연습> 탐욕법(Greedy)> 큰 수 만들기

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/42883>

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

 

문제설명: number로 주어지는 숫자들 중 k개 만큼 제거 후 남는 숫자들로 가장 큰 수를 만들어야 한다. 단 주의할 점은, 숫자들의 순서를 섞으면 안된다. 즉 앞에서부터 차례대로 제거하며 가장 큰수를 return 해야 한다.

 

[1차 시도]

def solution(number, k):
    number = list(number)
    cur = 1
    ans_len = len(number)
    while len(number)!= ans_len-k and cur!= len(number):
        if int(number[cur-1]) < int(number[cur]):
            h = cur
            while h!=0 and int(number[h-1]) < int(number[h]) and len(number)> ans_len-k:
                number.remove(number[h-1])
                cur-=1
                h-=1
        cur+=1
    return ''.join(number)

 

풀이: 먼저 number의 요소들을 숫자로 보기위해 리스트로 만들어주고 현재 위치와 앞의 위치 숫자의 대소비교를 위해 1번째 인덱스부터 시작하기 위한 cur 변수를 1로 설정한다. number에서 숫자를 제거하며 길이를 줄여나갈꺼기 때문에 ans_len으로 number의 길이를 저장해두었다.

 

while문으로 number배열에서 k개 만큼 숫자를 하나씩 제거하면서 number의 길이가 (처음 number배열-k)개가 될때까지 반복한다.

 

만약 앞의 숫자보다 현재 숫자가 크다면, 현재 숫자가 가장 클 때까지 즉 현재 숫자보다 작은 수들은 모두 제거해주어야 한다. 따라서 현재 인덱스를 h에 저장하고 h를 하나씩 줄이면서 왼쪽의 작은 숫자들을 number배열에서 remove 한다.

 

다 제거한 후 마지막에 join함수로 배열을 다시 문자열로 바꾸어 return 한다. 

 

 

채첨결과: 테스트케이스 10 시간초과와 테스트케이스 12 실패가 나온다.

 

 

해결방법: 테스트케이스 12번의 경우 만약 숫자가 모두 9로 이루어진 '99999'와 같은 number 문자열이라면, 제거대상이 아니므로 원 문자열 그대로 출력된다. 그리고 10번의 시간초과의 경우, 처음 배열로 변환하는 것과 remove함수를 사용하는 것에서 걸린 것 같다.  

 

 

[2차 시도]

def solution(number, k):
    cur = 1
    ans_len = len(number)
    while len(number)!= ans_len-k and cur!= len(number):
        if int(number[cur-1]) < int(number[cur]):
            h = cur
            while h!=0 and int(number[h-1]) < int(number[h]) and len(number)> ans_len-k:
                number = number[0:h-1] + number[h:]
                cur-=1
                h-=1
        cur+=1
    if len(number) == ans_len:
        return number[:len(number)-k]
    return number

 

풀이: 맨 처음 number를 배열로 만들지 않고, number를 슬라이싱으로 합쳐서 갱신하는 방법이다.

 

문자열 자체에는 remove나 pop을 사용하지 못하므로, while문을 돌면서 현재 위치의 값보다 작은 바로 왼쪽의 숫자를 제거하기위해 number 문자열에서에서 왼쪽 숫자보다 1개 앞의 숫자까지 자르고, 현재위치부터 끝까지를 잘라 아래와 이어붙이면 제거기능을 한다.

 

*cur=2인 경우,

 

h	number	number[0:h-1]	number[h:]	새로운 number
2	"4177252841"	"4"	"77252841"	"477252841"
1	"477252841"	""	"77252841"	"77252841"

 

k개 수 만큼 제거 완료 후, 만약 문자열 길이가 처음 number와 같다면, 즉 한 개도 제거되지 못했으므로 9만으로 이루어진 문자열임을 알 수 있다. 따라서 전체 길이중 k개를 뺀 길이를 슬라이싱으로 추출해 return해주었다.

 

이 경우가 아니라면, 알맞게 제거 후 number를 바로 return 한다.

 

 

채첨결과:  테스트케이스 10번이 7919.14ms으로 여전히 오래걸리긴 하지만 모든 테스트케이스가 정상적으로 잘 통과한다.