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

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

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

그리디 알고리즘에 속하는 문제.

저번에 포기했었는데 다시 풀어보니 풀려서 기분이 쪼끔 좋다.

def solution(number, k):
    answer = ''
    new = []
    start = 0
    
    # 일단 앞에서 k+1개 중에 가장 큰 수를 골라 그 수 앞에 있는 수들은 없애버림.
    tmp = number[:k+1]
    firstIdx = tmp.index(max(tmp))
    number = number[firstIdx:]
    k = k - firstIdx
    
    s = 0
    while k > 0:
        flag = True
        for i in range(s, len(number)-1):
            if int(number[i]) < int(number[i+1]):
                number = number[:i] + number[i+1:] 
                k = k - 1
                s = i - 1
                flag = False
                break
        # 만약, 앞 숫자가 뒷 숫자보다 작은 경우가 없을 경우(flag == true),
        # 전부 내림차순 정렬 되어있다는 것이므로, 끝에서 부터 남은 k개 만큼 제거해주면 된다. 
        if flag:
            return number[:len(number)-k]

    return number

내가 사용한 방법은, 코드에도 적어두었는데, 

 

1. 일단 앞에서 (k+1)개 중에 가장 큰 수를 골라 그 수 앞에 있는 수들은 없애 버림. 

==> max로 없앨 수 있는 개수가 k개 이므로, k+1번째 수 중에서 가장 큰 수를, 시작하는 숫자로 정해야한다. 그 뒤에 더 큰 숫자가 있다 한들 k개 이상 없애야 그 숫자로 시작할 수 있기 때문에 불가능하다.

 

2. 남은 숫자들 중에, 하나씩 index를 증가시켜 가며, 앞숫자가 뒷숫자보다 큰 경우, 앞숫자를 제거해준다. 

==> 앞숫자보다 뒷숫자가 크다는 것은, 앞숫자를 제거하면 숫자가 더 커진다는 것을 의미한다.

==> ex) 92456에서 1개를 제거해야할 때, 2<4이므로 2를 제거하는 것이 다른 숫자를 제거하는 것보다 더 큰 숫자를 만들 수 있게 한다. 

 

3. 만약, 앞 숫자가 뒷 숫자보다 작은 경우가 없을 경우, 전부 내림차순 정렬 되어있다는 것이므로, 끝에서 부터 남은 k개 만큼 제거해주면 된다. 

 

4. 중간에 있는 s의 역할은, s없이 range(len(number) - 1)을 하니 8번과 10번에서 시간초과가 났다.

==> i < i+1인 경우를 만나서 i번째 숫자를 빼줬다면, 그 다음부터는 다시 idx 0부터 검사할 것이 아니라, i-1부터 검사하면 된다.

그래서 s를 도입해서 다시 그 for문을 돌 때 더 효율적으로 돌 수 있게 했다.