[프로그래머스/JAVA] 고득점Kit > 탐욕법(Greedy) > 큰 수 만들기 (by 다알쥐AI)

고득점Kit > 탐욕법(Greedy) > 큰 수 만들기

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

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

 

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

 

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

 

제한 조건

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

입출력 예

---

[간단설명]

숫자중에서 k 개 제거했을 때, 가장 큰 수 구하기

 

[접근방법]

1. 스택을 만든다.

2. 모든 문자를 char로 꺼내서 비교한다.

3. 앞에 숫자가 뒤에 숫자보다 작으면 제거한다.(Greedy알고리즘)

4. remove카운트가 k개가 될때까지 반복한다.

5. 제거된 최종 문자열을 리턴한다.

 

[주의사항]

1. 스택을 이용하면 직전 문자를 알수 있기 때문에 용이하다.

2. 앞에 숫자가 뒤에 숫자보다 작으면 제거를 하고, 다시 앞에 숫자가 뒤에 숫자보다 작을 수도 있다.

3. 모든 숫자가 앞에 숫자가 뒤에 숫자보다 큰 경우도 있다.

-> remove 카운트가 k가 될 때까지 확인하자

4. 스택은 후입선출이기 때문에 String으로 만드는 과정이 복잡하다.

-> 다양한 방법을 찾아보자

 

[소스공개]

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        
        // remove 카운트
        int remove = 0;
        
        // 문자 비교용 stack
        Stack<Character> stack = new Stack<>();
        
        // 모든 문자를 검사한다.
        for(char c : number.toCharArray()){
            // 1. remove 카운트가 k 보다작으면
            // 2. stack이 비어있지 않으면
            // 3. stack이 c보다 작으면
            // 즉, 앞에 숫자가 뒤에 숫자보다 작으면 삭제
            while(remove<k && !stack.isEmpty() && stack.peek()< c){
                stack.pop(); // 삭제
                remove++;    // remove 카운트 증가
            }
            // stack에 넣는다 
            stack.push(c);
        }
        // remove카운트가 k만큼 돌지 않았다면
        // 즉, 숫자 비교시 앞에 숫자가 뒤에 숫자보다 작지 않은 경우
        while(remove<k && !stack.isEmpty()){
            stack.pop();
            remove++;
        }
        // 스택은 후위 연산이기 때문에, LinkedList로 재구성한다.(원래 문자로)
        LinkedList<Character> list = new LinkedList<>();
        while(!stack.isEmpty()){
            list.addFirst(stack.pop());
        }
        
        // String 버퍼에 재구성한 문자를 넣는다
        StringBuffer sb = new StringBuffer();
        for(Character c : list){
            sb.append(c);
        }

        // String 버퍼를 String으로 변환하여 리턴 
        return sb.toString();
    }
}

 

[실행결과]