Programmers / 큰 수 만들기 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 큰 수 만들기 (2단계)

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/42883

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

문제 설명

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

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

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

제한 조건

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

입출력 예numberkreturn

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

나의 풀이 (처음풀이 / 오답)

def solution(number, k):
    answer = ''
    arr = []
    for i in number:
        arr.append(i)
    
    for _ in range(k):
        arr.pop(arr.index(min(arr)))
    
    return "".join(arr)

리스트 내에수 가장 작은 수 먼저 제거 하는 방법은 테스트 3에서 오류가 생김

 

풀이 2. Stack 구조 이용

 

def solution(number, k):
    answer = ''
    arr = [] #stack LIFO 구조 이용
    for num in number:
        n = int(num)

        while arr and k > 0 and arr[-1] < n:
            k -= 1
            arr.pop()
        arr.append(n)
        
    for i in arr:
        answer += str(i)
        
    return answer

 

 

테스트 12번에서 막혔다..

 

https://programmers.co.kr/questions/25756

다른 유저분이 친절하게 질문 목록에 그 이유를 작성해주셨다.

K가 모두 소진되지 않았을 때를 고려해야하고 코드를 짜야하는 것이다... 

 

 

 while문 코드와 비교해서 보면 다음과 같다.

        while arr and k > 0 and arr[-1] < n:
            k -= 1
            arr.pop()
        arr.append(n)

987654321 수에 k= 5라고 하면

k = 5, arr = [9] 

k = 5, arr = [9,8] (9 = arr[-1] < 8 = n, while문을 그냥 지남)

이런 식으로 k가 소진되지 않고 계속해서 arr에 해당 값이 저장될 것이다.

 

따라서 소진되지 않은 k 만큼 숫자를 삭제하고 반환해야하므로 마지막 return 값을 수정해준다.

 

 

최종 답안

def solution(number, k):
    answer = ''
    arr = [] #stack LIFO 구조 이용
    for num in number:
        n = int(num)

        while arr and k > 0 and arr[-1] < n:
            k -= 1
            arr.pop()
        arr.append(n)
    if k > 0:
        arr = arr[:-k]
    
    for i in arr:
        answer += str(i)
    return answer

---

※ 알아야 할 것

- K 값이 소진되지 않는 경우를 고려해야한다. 

- Stack 구조를 이해하여 코드를 짜야함

 

.