[Python 파이썬] 프로그래머스 - 큰 수 만들기

2024년 6월 10일

문제 링크 : 프로그래머스 - 큰 수 만들기

 

---

문제 접근

 

주어진 숫자 number에서 k개의 수를 제거하여 도출될 수 있는 가장 큰 수를 구하면 된다.

 

이는 아주 그리디하게 접근 가능하다.

최대한 큰 수가 앞자리 수에 오도록 유도하는 것이다.

이에 나는 스택 구조를 활용하여, 최대한 앞자리에 오는 작은 수를 먼저 없애는 것에 초점을 두었다.

 

1924를 예로 보자.

 

 

k는 2이고, 가장 첫 번째 자리수는 1이다.

stack이 비어있기에 비교할 대상이 없어 now를 append 해준다.

 

 

now는 9이고, stack의 마지막 요소는 1이기에 맨 앞 자리수에 1보단 9가 오는게 수가 더 클 것이다.

이에 stack의 마지막 요소가 now보다 크거나 같은 값일 때까지 pop 하며 k를 1씩 감소시킨다.

이후 now를 stack에 append해준다.

 

 

now는 2이고, stack의 마지막 요소는 9다. 2보다 9가 더 크기에 stack에 append 해준다.

 

 

now는 4이고, stack의 마지막 요소는 2이다. 해당 자리수에는 2보다 4가 오는게 더 수가 클 수 있고, 아직 삭제 횟수가 남아있기에 stack의 마지막 요소를 pop 해주고 now를 append 한다.

 

 

k = 0으로 더 이상 삭제할 수 없고, 주어진 숫자의 모든 자리수를 확인해 보았다.

따라서, 1924에서 수 2개를 삭제하여 나타낼 수 있는 가장 큰 수는 94이다.

 

다른 예시도 보자.

 

number = 4177252841

 

 

 

모든 자리수가 같은 수인 경우는 어떨까?

 

number = 22222

 

 

로직대로라면 stack의 마지막 요소보다 now가 클 경우에면 pop 해주므로, 위 과정에서 pop되는 과정은 없다.

하지만 k개를 무조건 삭제해야 하기 때문에 최종 stack에서 k번 만큼 pop 해주어야 한다.

왜 마지막 요소부터 삭제해야 하는가? 다음과 같은 경우 때문이다.

 

 

위 수는 앞 자리수보다 뒷 자리수가 작아지는 내림차순 형태이기 때문에, 22222 처럼 최종 stack까지 하나도 pop되지 않고 그대로 append 될 것이다.

하지만 무조건 k개를 삭제해야 한다. 앞자리 수가 무조건 더 크기 때문에, 맨 뒷자리 수부터 삭제해야 하므로 맨 뒷자리 수를 k번 pop해주는 것이 무조건 큰 수가 될 수 있다.

 

---

전체 코드

 

def solution(number, k):
    stack = []
    for i in range(len(number)):
        while stack and k > 0 and stack[-1] < number[i]:
            stack.pop()
            k -= 1

        stack.append(number[i])

    while k > 0:
        stack.pop()
        k -= 1

    return "".join(stack)

if __name__ == "__main__":
    number = "4177252841"
    k = 4

    print(solution(number, k))

---

풀이 후기

 

그리디하게 접근하고 시간복잡도를 챙기기 위해 스택 자료구조를 활용해 효율적으로 문제를 풀려고 노력했다.

이런 문제가 그리디 알고리즘 유형의 정석이라고 생각한다.