[프로그래머스] 큰 수 만들기 (Python) / level2 / 그리디

Programmers Logo

 

 

Contents

---

1.  문제

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

문제와 제한 조건

쉽게 말하면 number(문자열)과 k(정수)가 주어졌을 때, number에서 k개의 숫자를 뺐을 때 만들어지는 가장 큰 수를 출력하라는 것입니다.

 

1) 예제 입출력

예제 입출력

number="1924"이고, k=2 일 때, 1과 2를 빼서 "94"를 만든 게 가장 큰 수입니다.

 

 

2. 핵심 논리⚡️

풀이의 핵심 논리는 맨 앞자리수가 클수록 숫자는 커진다는 점을 이용합니다. 스택을 이용해서 맨 앞자리부터 순차적으로 수를 하나씩 검사하며, 앞자리 수를 가능한 크게 만드는 선에서 k개의 숫자를 제외시키는 것입니다.

3. 풀이✅

1) 코드

def solution(number, k):
    stack = []
    for n in number:
        while len(stack)>0 and k>0 and stack[-1]<n:
            stack.pop()
            k -= 1
        stack.append(n)
    if k:
        return number[:-k]
    else:
        return "".join(stack)

스택의 의미: 맨 앞 자릿수를 크게 만들기 위한 임시 저장소입니다.

주어진, number를 1개씩 반복합니다.

아래 3가지 조건이 만족할 때, 스택에서 숫자 한 개를 빼서 버리고, k -= 1을 해줍니다.

1. 스택에 원소가 있고
2. k가 0보다 크고
3. 새로 넣을 숫자가 스택 마지막 원소보다 크면

for문이 끝났는데 k가 남아있는 경우, 예를 들어 number=“54321”, k=2 가 들어왔을 때 스택의 마지막 원소가 항상 새로 넣을 수보다 크기 때문에 k=2가 그대로 남게 됩니다. 이럴 때는 뒤에서 k개만큼 제외하고 출력해야 합니다. “54321”[:-2]를 하면, “543”이 출력됩니다. (뒤에서 2개 제외)

 

2) 다른 풀이

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

1번 풀이도 짧지만, 더 짧게 푼 풀이입니다. return 하는 부분에서 스택의 슬라이싱을 st[ : len(number)-k]로 통일했다는 점이 위 풀이와의 차이점입니다. 이게 가능한 이유는 number="4312", k=2 예시를 보면 좋습니다. for 문이 끝나는 시점에 스택(st)에는 ["4", "3", "2"]가 남아있고, k=1 일 것입니다. 이럴 때, number개수 4에서 1을 빼준 3을 앞에서부터 출력하면 "432"가 출력되어 정답이고, 그 외에 for문이 끝났을 때, k=0인 모든 경우에 스택(st)의 모든 값을 다 출력하면 정답 입니다.

 

처음에 푸는 방법을 찾기까지도 조금 시간이 걸렸지만, 이렇게 풀어야지 하고 코드로 구현하는데도 시간이 많이 걸린 문제였습니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익하고 재미있는 글로 찾아오겠습니다.

 

 

Reference)
1. Programmers Logo: https://programmers.co.kr/