[프로그래머스] 42883 큰 수 만들기 (python 파이썬)

프로그래머스

---

개인적으로 좀 어려웠던 문제. 로직을 짜는 사고과정을 더 명확하게 할 필요가 있는 거 같다.

---

아이디어

기본적으로 큰 수를 만들려면 앞자리가 커야 한다 (8xxx < 9xxx)

 

그럼 앞자리부터 큰 수를 두려고 생각할 것이다. 앞자리에 큰 수를 어떻게 채울 수 있을까?

 

문제에서 숫자 한 개를 주고 K개의 수를 제거해서 최대로 만들라고 한다.

 

탐색 방향은? 앞에서부터 순서대로 탐색한다. 두 수를 비교해 가며 수를 버릴지 말지 결정하면 된다.

 

예제에 있는 4177252841을 가지고 설명하면, 먼저 4를 리스트에 담아준다. [4] , k = 4

 

4 다음은 1이니까 4보다 작다. 따라서 1도 넣어준다. [4, 1], k = 4

 

그다음 7이 나왔다. 7은 앞에 1보다 크다. 그럼 앞에 넣었던 수를 빼고 넣어야 한다. 1을 빼주자.

숫자를 한 개 제외했으므로 k값도 감소시켜 준다. [4], k = 3

 

이제 4와 비교를 해보자. 여전히 7이 크다. 4도 빼주자. [], k = 2

이제 7을 넣어주자. [7] k = 2

 

그다음 숫자는 또 7이다. 숫자가 같으니까 넣어준다. [7, 7] k = 2

이 방식대로 쭉 진행해 보면 다음과 같은 과정으로 진행된다.

 

1. [], k = 4

2. [4], k = 4

3. [4, 1], k = 4

4. [4], k = 3

5. [], k = 2

6. [7], k = 2

7. [7, 7], k = 2

8. [7, 7, 2], k = 2

9. [7, 7], k = 1

10. [7, 7, 5], k = 1

11. [7, 7, 5, 2], k = 1

12. [7, 7, 5], k = 0

13. [7, 7, 5, 8], k = 0

 

k값이 0이면 더 이상 숫자를 제외할 수 없다. 뒤에 남은 건 붙여주자.

[7, 7, 5, 8] + [4, 1] = [7, 7, 5, 8, 4, 1]

 

그리고 이 케이스에서는 없지만, 이렇게 만든 리스트가 문제에서 요구한 정답의 길이보다 긴 경우도 고려해야 한다.

리스트 슬라이싱으로 정답크기에 맞게 잘라주자. 

 

---

전체 코드

def solution(number, k):
    
    answer = ''
    
    num_list = [int(x) for x in list(number)] # 숫자를 한개씩 나눠 리스트로 저장
    box = [] # 숫자를 담을 리스트
    
    num_length = len(number) - k # 문제에서 요구하는 리스트 크기
    
    for i in range(len(number)):
        while k > 0 and box and box[-1] < num_list[i]: # k > 0, 리스트 안 비어있고, 새로운 값이 크면 pop진행
            box.pop()
            k -= 1
            
        if k == 0: 
            box += num_list[i:] # 뒤에 남은 숫자들 붙여줌
            break # k가 0이면 더이상 이 과정을 진행할 수 없으니까 break
        
        box.append(num_list[i]) # 숫자 추가
        
    if len(box) > num_length: #숫자를 담은 리스트가 정답길이보다 길면 슬라이싱
        box = box[:num_length]
    
    answer = ''.join(map(str,box)) #리스트들 join함수로 합쳐줌
    
    return answer