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

이번 문제는 Greedy 문제입니다.

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42883

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

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

---

큰 수는 자리수가 큰 부분이 중요하죠. 자리수가 큰 부분의 값이 크면 됩니다.

 

처음에 푼 풀이법과 최종 답안을 비교해볼건데요, 먼저 처음 풀이법의 아이디어는 아래와 같습니다.

'인덱스가 앞에서부터 차례대로 움직이며, 만약 현재의 값이 다음 오는 값보다 작은 경우 현재의 값은 제거된다.'

이에 따라 작성한 코드는 다음과 같습니다.

def solution(number, k):
    answer = ''

    list_num = list(number)

    cnt_del = 0

    # 현재 값이 뒤에 나오는 값보다 작은 경우 삭제
    while cnt_del < k:
        len_list = len(list_num)

        flag = False
        idx_del = 0
        for i in range(len_list - 1):
            if list_num[i] < list_num[i+1]:
                flag = True
                idx_del = i
                break

        if flag:
            list_num.pop(idx_del)
            cnt_del += 1
        else:
            for _ in range(k - cnt_del):
                list_num.pop()
            break

    answer = ''.join(list_num)

    return answer

 

이 코드의 문제점은 시간복잡도에 있습니다.

number은 1,000,000자리 이하인데 문자를 삭제할 때마다 계속 인덱스 0부터 탐색하고,

게다가 pop()이 아닌 인덱스를 지정한 pop을 수행하기 때문에 실행시간은 그만큼 더 길어질 수 밖에 없습니다.

그래서 시간초과로 인해 정답이 될 수 없었습니다.

 

개선해야하는 부분은 다음과 같았습니다.

1. pop을 할 때마다 인덱스 0부터 탐색하는 로직

2. 인덱스를 지정한 pop ( → 이제 웬만하면 코테에서 사용하지 않으려구요!)

---

다른 분들의 풀이를 참고하여 새로 작성한 풀이는 아래와 같습니다.

def solution(number, k):
    answer = ''
    idx_cur = 0
    num_del = 0
    list_sel = []

    while num_del < k and idx_cur < len(number):
        # 리스트의 길이가 0이거나, 리스트의 제일 끝 값이 현재 값보다 크거나 같은 경우 일때 까지 pop
        while list_sel and list_sel[-1] < number[idx_cur] and num_del < k:
            list_sel.pop()
            num_del += 1
        list_sel.append(number[idx_cur])
        idx_cur += 1

    if num_del < k:
        answer = ''.join(list_sel[:len(number) - k])
    else:
        answer = ''.join(list_sel + list(number)[idx_cur:])

    return answer

 

첫 풀이와의 차이점

• 기존 string배열 number의 원소를 삭제하는 것이 아닌, 새로운 배열 list_sel을 통해 return할 원소들을 저장해줌
  → 인덱스를 지정한 pop을 사용하지 않게 됨

주의점

• num_del 이 아닌 num_sel(list_sel의 크기)로 판단하면 안됨

 

먼저 정답 풀이의 아이디어에 대해 설명하겠습니다. 글로 설명하면 복잡해지니, 그림으로 대신할게요.

 

그리고 num_sel(list_sel의 크기)로 판단하면 안되는 이유는 

number = "1924", k = 2 일때를 생각하면 알 수 있습니다.

idx_cur이 2일 때 list_sel은 list_sel[0]: 9, list_sel[1]: 2가 됩니다.

그리고 나서 idx_cur이 3일 때 이미 선택되어진 숫자의 개수가 2이므로 while문을 돌지 않고 조건문을 빠져나가게 됩니다.

4가 2보다 크므로 이는 정답이 아닙니다.

 

원소를 삭제할 때는 확정된 것이지만(선택을 되돌리는 경우가 없음),

list_sel에 append되었다고 해서 해당 숫자가 반드시 정답에 포함된다는 보장은 없습니다.

 

이번 문제는 난이도가 꽤나 있는 문제였던 것 같습니다.