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

문제

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

풀이

풀이 1 - (시간초과)

1. itertools.combinations 함수를 사용하여 my_list에서 가능한 모든 조합을 생성한다. 여기서 len(number) - k 개수만큼의 숫자를 선택한 조합을 생성한다.
2. sorted 함수를 사용하여 조합들을 정렬한다. 정렬되면 가장 큰 숫자가 마지막에 위치하게 한다.
3. 선택된 가장 큰 숫자 조합인 new_num을 문자열로 합치기 위해 join 함수를 사용한다.

import itertools 
def solution(number, k):
    answer = ''
    my_list = [i for i in number]
    new_num= sorted(list(itertools.combinations(my_list,len(number)-k)))[-1]
    return "".join(new_num)

풀이 2 - (10번 테스트케이스 실패)

itertools.combinations를 사용하여 모든 조합을 생성하고 정렬한다. 이러한 방식은 입력값이 큰 경우에는 매우 비효율적이기 때문에 시간 복잡도가 크게 증가하여 시간 초과가 발생할 수 있다.

예를 들어, 숫자 문자열의 길이가 10이고 k가 5라면, combinations를 사용하여 길이가 5인 모든 조합을 생성하는 과정에서 10개의 숫자 중 5개를 선택하는 조합의 수는 매우 크며, 이 모든 조합을 생성하고 정렬하는 데에 상당한 시간이 소요될 수 있다.

1. goal은 만들어야 할 숫자의 길이를 나타낸다.
2. result는 최종적으로 만들어질 가장 큰 숫자를 담을 변수이다.
3. start는 현재 숫자 선택이 시작되는 인덱스를 나타내며 0으로 초기 세팅을 한다.
4. result의 길이가 goal보다 작은 동안 특정 단계를 수핸한다.
5. number 리스트에서 start부터 len(number) - goal + len(result) + 1까지 슬라이싱하여 해당 범위의 숫자들을 추출한다.
6. 추출된 숫자들 중 가장 큰 숫자를 max_num으로 설정한다.
   7.number 리스트에서 max_num을 start 인덱스부터 검색하여 가장 처음 발견되는 인덱스를 찾는다. 이 인덱스를 max_idx로 저장한다.
7. max_num을 result에 추가합니다.
8. start를 max_idx + 1로 업데이트하여 다음 숫자 선택이 시작되는 위치를 설정한다.

(Tip!)
파이썬의 index() 함수는 리스트나 문자열과 같은 시퀀스 타입에서 특정 값의 인덱스를 찾는 데 사용됩니다. 이 함수는 기본적으로 하나의 인자만 받아서 그 값의 첫 번째 등장하는 인덱스를 반환합니다.

하지만 두 개의 인자가 들어가면, 첫 번째 인자는 찾으려는 값이고, 두 번째 인자는 검색을 시작할 위치입니다. 즉, index(value, start) 형태로 사용됩니다. 이 경우에는 value 값이 start 인덱스부터 시작해서 처음으로 나타나는 위치의 인덱스를 반환합니다.

def solution(number, k):
    goal = len(number) - k
    result = ''
    start = 0
    
    while len(result) < goal:
        max_num = max(number[start:len(number) - goal + len(result) + 1])
        max_idx = number.index(max_num, start)
        result += max_num
        start = max_idx + 1
    
    return result

풀이 3 - (성공)

주어진 문제는 크게 두 부분으로 나뉘어진다:

• 주어진 숫자 문자열에서 숫자를 선택하여 만들 수 있는 가장 큰 숫자를 구하는 것
• 선택된 숫자가 최종적으로 원하는 개수만큼 선택되어야 하는 것.

여기서 9가 가장 큰 숫자이므로, 만약 선택할 숫자가 아직 남아 있다면 항상 9를 선택하면 된다. 즉, 선택할 수 있는 숫자의 개수가 남아 있을 때는 9를 선택하고, 그렇지 않은 경우에는 현재 남아 있는 숫자 중 가장 큰 숫자를 선택하면 된다.

• 빈 리스트 stack을 생성하여 나중에 선택된 숫자들을 임시로 저장하는 용도로 사용한다.
• number 문자열에 있는 각 숫자를 순회하면서 아래의 과정을 수행한다.
• while 루프를 사용하여 현재 숫자 num과 stack의 마지막 숫자를 비교한다.
• 만약 stack이 비어있지 않고(stack에 숫자가 있는 경우), 아직 제거해야 할 숫자 개수 k가 0보다 크며, stack의 마지막 숫자가 현재 숫자 num보다 작다면, stack의 마지막 숫자를 제거하고 k를 1 감소시킨다.
• 위 과정을 거치면서 stack에 있는 숫자들 중 현재 숫자 num보다 작은 숫자들을 모두 제거한다.
• 그리고 나서 현재 숫자 num을 stack에 추가한다.
• k에 남은 제거 횟수가 남게 될 수 있기 때문에 추가적으로 k가 0보다 큰 동안은 stack에서 숫자를 제거한다. 이는 남아 있는 숫자들 중에서 아직 제거되지 않은 숫자들을 제거하는 것이다.
• 최종 stack내 문자열을 순서대로 합쳐서 answer에 저장하고 반환한다.

def solution(number, k):
    stack = []
    
    for num in number:
        while stack and k > 0 and stack[-1] < num:
            stack.pop()
            k -= 1
        stack.append(num)
    
    while k > 0:
        stack.pop()
        k -= 1
    
    answer = ''.join(stack)
    return answer

reference

• 그리디 알고리즘 정리글
• stack 정리글