[JAVA] 큰 수 만들기 (코딩테스트 고득점 Kit [ Greedy(탐욕법) ]) - LEVEL2

📂문제 설명

 

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

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

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

 

제한 조건

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

입출력 예

numberkreturn

1924	2	94
1231234	3	3234
4177252841	4	775841

 

---

📂아이디어 및 알고리즘(문제 풀이)

• 1,000,000 C 100,000,000-k 를 하게 되면 엄청난 시간이 걸리기 때문에 조합으로 문제를 해결하려 하면 안된다.
• 그래서 한번 순회 하면서 수를 최대로 만들면서 제거해 나가야 한다.
• 그러기 위해서 StringBuilder를 이용하여 해당 index를 쉽게 제거할 수 있도록 한다.[ num.deleteCharAt(index) ]
  • index-- 를 통해서 제거한 index에서 하나를 땡겨주는 역할을 한다.
• while문에서는 제거하는 수가 k보다 작을때까지 순회 하도록 설계 하였고
• 첫번째 if문 에서는 수를 제거할때 index가 1보다 같거나 클때와 index-1 < index일때 조건을 걸었다. 이는 첫번째 index = 0일때는 제외하여 생각하여 조건을 걸어주었다.
• 첫번째 else문 에서는 index -1 >= index 로 수를 제거하는 조건이 아닌 다음 index로 보내는 작업을 한다.
  • 두번째 if문에서는 index가 n번째일때를 고려하여 [ 마지막 index <= index-1 ] 일때 마지막 n번째 수를 제거하는 조건을 의미한다. 

📂소스 코드

class Solution {
    public String solution(String number, int k) {
 
        StringBuilder num = new StringBuilder(number);
        int delete_cnt =0;
        int index=0;
        int i=0;
        
        while(delete_cnt < k) {
            
            if(index >= 1 && num.charAt(index-1) < num.charAt(index)) {
                num.deleteCharAt(index-1);
                index--;
                delete_cnt++;
            }
            else {
                if(index == num.length()-1 && num.charAt(index) <= num.charAt(index-1)) {
                    num.deleteCharAt(index);
                    index--;
                    delete_cnt++;
                }
                else {
                    index++;
                }
            }     
        }
        return num.toString();
    }
}

 

📂코드 결과

 

📂후일담

StringBuilder에 delete기능을 처음 써보게 되어서 이렇게 편리한게 있나 싶었다. 정말로 코딩을 창의적으로 잘하는것도 중요하지만 효율적으로 JAVA의 라이브러리를 잘 이용하는것도 중요하다고 느꼈다. 매 문제마다 하나씩 알아가는거 같아서 이렇게 블로그 포스팅 하는게 귀찮지만 얻어가는게 많다고 생각한다.✨