프로그래머스 : 큰 수 만들기 [그리디, Lv2, 자바, 파이썬]

 

프로그래머스

[문제 설명]

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

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

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. 

number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 
가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

[제한 조건]

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

[입출력 예]

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

[문제 풀이]

1. 유형 파악

처음 문제를 봤을 때 조합이 생각났는데, 제한 조건 때문에 메모리 초과 이슈도 있고

number의 순서를 지키면서 숫자를 제거해야되기 때문에 불가능했다.

>> 완전 탐색 방법 불가능

 

따라서 그리디 방식으로 문제를 풀었다.

 

2. 문제 풀이

입력받은 수에서 가장 큰 수를 만드려면 가장 앞에 있는 수가 큰 수여야한다. 

앞의 수를 큰 수로 만들기 위해서 k번 수를 제거하며 현재까지 저장된 수가 가장 큰 수가 되게 한다. (스택 사용)

배열 끝까지 가면서 이 과정을 진행하고 제거할 수가 남았다면 배열의 뒤부터 남은 수만큼 숫자를 제거한다.

 

[과정]

1) 주어진 number의 값을 하나씩 확인하는 반복문 실행

2) 스택이 비어있거나, 제거할 수가 안남았거나, 이전 요소가 현재 값보다 작다면 이전 요소를 제거하고, 현재요소를 스택에 넣음

3) while문을 실행하며 스택에 남아있는 이전 요소들도 현재 요소와 비교해 2)번 과정을 반복 (작다면 이전 요소 제거, 현재요소 스택 삽입)

4) k번 수를 모두 제거했으면 그대로 스택을 반환. 반복 후에도 k번 수가 제거되지 않았으면 결과 맨 뒤부터 순서대로 남은 수만큼 제거

 

[정답 코드]

자바 코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        Stack<Character> stack = new Stack<Character>();
        char cur;
        char next;
        
        for(int i=0;i<number.length();i++) {
            next = number.charAt(i);
            while(!stack.isEmpty() && k>0){
                cur = stack.pop();
                if (cur < next) {
                    k--;
                }
                else {
                    stack.add(cur);
                    break;
                }
            }
            stack.add(next);
        }
        while(k>0){
            stack.pop();
            k--;
        }
        
        for(char s : stack) {
            answer.append(s);
        }
        
        return answer.toString();
    }
}

파이썬 코드

def solution(number, k):
    answer = []

    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)

    return ''.join(answer[:len(answer) - k])

 

 

길이가 많이 차이나지만 같은 로직임