[프로그래머스][LV.2] 큰 수 만들기 | python3

문제링크:  큰 수 만들기

---

문제설명

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

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

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

 

제한조건

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

---

 

문제풀이

def solution(number, k):
    answer = ''
    number=sorted(list(number),reverse=True)
    answer=''.join(number[:len(number)-k])
    return answer

문제 이해를 잘못함ㅋㅋㅋㅋ숫자 순서는 그대로여야하구나..

 

from itertools import combinations

def solution(number, k):
    answer=0
    comb=list(combinations(number,len(number)-k))
    # print(comb)
    for num in comb:
        # print(num)
        n=''.join(num)
        answer=max(answer,int(n))
    return str(answer)

combinations로 푸니 시간초과가 난다.

 

 

힌트를 봤다.

앞의 숫자가 뒤의 숫자보다 크면 된다.

앞의 수가 뒤의 숫자보다 작으면 빼야함 => stack

나의코드

def solution(number, k):
    
    stack=[]
    for n in number:
        
        while stack and stack[-1]<n and k>0: # stack의 마지막 원소가 넣으려는 값보다 작으면 빼기
            stack.pop()
            k-=1
        stack.append(n)
    if k>0:
        stack=stack[:-k]
    answer=''.join(stack)
    return answer

 

---

 

참고하기

def solution(number, k):
    answer = ''  # 최종적으로 만들어질 가장 큰 수를 저장할 문자열
    max_v, max_index, a_len = number[0], 0, len(number) - k  
    # len(number) - k :: 남겨야 할 숫자의 개수 (전체 길이 - 제거할 개수)
    
    while a_len:  # 남겨야 할 숫자가 존재하는 동안 반복
        # 남겨야 할 숫자가 1개라면, 남은 숫자 중 최댓값을 찾고 반환
        if a_len == 1:
            answer += max(number[max_index:])  # max_index부터 끝까지의 숫자 중 최댓값 추가
            return answer  # 정답 반환

        # 현재 선택할 수 있는 범위에서 최댓값을 찾음
        # 선택할 수 있는 범위: max_index부터 (전체 길이 - 남은 숫자 개수 + 1)까지
        max_v = max(number[max_index: -a_len+1])
        
        # 최댓값이 있는 위치를 찾고, max_index를 갱신하여 다음 탐색을 진행
        max_index += number[max_index: -a_len+1].index(max_v)
        
        # 찾은 최댓값을 정답 문자열에 추가
        answer += max_v
        
        # 다음 숫자를 고려하기 위해 인덱스를 1 증가
        max_index += 1
        
        # 남겨야 할 숫자의 개수를 하나 줄임
        a_len -= 1

    return answer

인덱스 슬라이싱을 이용한 풀이

test 10 에서 시간 초과가 난다고 하지만 이렇게 스스로 생각해서 풀어보는 게 좋은 것 같다.

근데 가장 큰 수가 뒷쪽에 있다거나 하면 틀릴 수도 있을듯

 

 

---

🚨 반례 찾기

아래와 같은 경우, 현재 코드가 잘못된 답을 반환할 가능성이 있습니다.

✅ 반례 1

number = "987654321"
k = 4
print(solution(number, k))  # 정답: "98765"

📌 코드의 실행 과정

• 남길 숫자 개수: len(number) - k = 5
• max(987654) → 9 선택 → "9"
• max(87654) → 8 선택 → "98"
• max(7654) → 7 선택 → "987"
• max(654) → 6 선택 → "9876"
• max(54) → 5 선택 → "98765"

🔹 결과는 맞음! 그러나 지금까지는 내림차순이었기 때문에 문제가 안 됨.

---

✅ 반례 2 (잘못된 결과 발생)

number = "1231234"
k = 3
print(solution(number, k))  # 정답: "3234" (예상되는 결과)

📌 코드의 실행 과정

1. 남길 숫자 개수: 4
2. max(1231) → 3 선택 → "3"
3. max(231) → 3 선택 → "33"
4. max(1) → 2 선택 → "332"
5. max(34) → 4 선택 → "3324"

🚨 결과: "3324" (오답)
✅ 정답: "3234"

💡 문제점

• max()를 사용할 때 앞에서부터 가장 큰 값만 먼저 고르는 방식이 최적해를 보장하지 않음
• number[max_index: -a_len+1]에서 가장 큰 숫자를 찾을 때, 앞에 작은 숫자가 포함될 수도 있음