[Programmers] Level 2. 큰 수 만들기 (Python)

🔗 Problem Link

프로그래머스

---

❔Thinking

• 주어진 숫자에서 k개의 수만을 제거하고 이어 남은 숫자를 이어붙인다.
• 이어 붙인 숫자들 중 가장 큰 숫자를 반환한다.
• 숫자는 순서를 그대로 유지한 채로 제거하거나 이어붙인다.

---

💻Solution

1. 주어진 수를 최대로 만드는 숫자의 위치를 찾아가는 풀이

def solution(number, k):
    answer = ''
    while k >= 0:
        max_num = 0
        if k == 0 or len(number) == 1:
            answer += number
            break
        for i in range(len(number[:k+1])):
            if number[:k+1][i] == '9':
                start_cur = i
                break
            if max_num < int(number[:k+1][i]):
                max_num = int(number[:k+1][i])
                start_cur = i
        if start_cur == 0:
            answer += number[0]
            start_cur += 1
        else:
            k -= start_cur
        number = number[start_cur:]
    if k != 0:
        return answer[:-1]
    return answer

 

2. stack을 활용한 풀이

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

---

🗝️keypoint

1. 주어진 수의 순서를 그대로 가져가기 때문에, 가장 작은 숫자들을 제거하는 방법은 적합하지 않다.
2. 수를 최대로 만드는 방법은, 조건에 맞게 왼쪽부터 큰 숫자만을 남기는 것이다.
3. 10진수는 0~9까지 이기 때문에, 9보다 큰 숫자가 나올 수 없다. (시간 초과를 피할 수 있는 방법 중 하나이다.)
4. 주어진 수의 끝까지 확인했음에도 k가 0이 아닌 경우, 마지막 숫자를 제거하여 해결할 수 있다.