[programmers] 프로그래머스 큰 수 만들기(Python)

(주)그렙

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

(Python)

(글쓴날 : 2020.06.17)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 큰 수 만들기

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42883

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

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

숫자로 이루어진 문자열이 주어지고, 해당 문자열에서 k개의 수를 제거해 가장 큰 수를 만드는 문제입니다.

 

저의 경우, 그리디를 적용하였고, Python을 사용했습니다.

가장 큰 수를 만들 수 있는 규칙은 앞에서부터 수들을 탐색하여 만약 탐색했던 수 보다 큰 수가 나올 경우 이전에 탐색된 수들을 제거하는 것입니다.

이를 위해, 이전에 탐색했던 수들을 스택에 저장하였고, 현재 탐색 중인 수와 스택에 저장되어 있는 수들을 비교해 만약 스택에 저장된 수가 더 작을 시 제거함과 동시에 k를 1씩 감소시킨 뒤, 더 이상 제거할 수가 없을 때 현재 탐색 중인 수를 저장하였습니다.

그렇게 탐색을 해나가다 k가 0이 될 경우 스택에 저장된 수 + 탐색할 남은 수들이 가장 큰 수가 되며, k가 0이 아닌 상태로 탐색이 끝날 경우 스택에 저장된 수의 뒤에서부터 k개 만큼 제거하면 가장 큰 수가 됩니다.

마지막으로, join() 함수를 통해 가장 큰 수로 기록된 스택을 문자열로 바꾸어 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

def solution(number, k):
    stack = []
    
    for i in range(len(number)):
        if not stack:
            stack.append(number[i])
            continue
        
        isRemove = False
        
        while stack and int(stack[-1]) < int(number[i]):
            stack.pop()
            k -= 1
            if not k:
                isRemove = True
                stack += number[i:]
                break
        
        if isRemove:
            break
        
        stack.append(number[i])
        
    return "".join(stack[:len(number) - k]) if k else "".join(stack)

---