99클럽 코테 스터디 20일차 TIL , 큰 수 만들기

문제

풀이

받은 문자열에서 순서를 바꾸지 않고 k개의 숫자를 제거했을 때 가장 큰 수를 출력하면 되는 문제이다.

 

제출 1 - 정답

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        
        int len = number.length() - k;
        int idx = 0;
        
        for(int i=0;i<len;i++){
            char max = '0';
            for(int j=idx;j<=k+i;j++){
                if(number.charAt(j) > max){
                    max = number.charAt(j);
                    idx = j + 1;
                }
            }
            sb.append(max);
        }
        return sb.toString();
    }
}

 

뒤에 항상 보험을 든다고 생각했다.

예를 들어 문자열의 길이가 다섯 글자고 k가 2라면  세 글자를 만들어야 한다.

그래서 처음 문자열에서 k를 빼고 그만큼 반복문을 돌게된다.

내부의 반복문에서는 글자 수에서 찾을 수 있을 만큼 그러니까 0 인덱스의 자리에서는 k만큼 도는 거다. 뒤에 두 글자의 여유를 남겨두고 최대의 값을 찾는 거다.

그런 식으로 그리디 알고리즘을 적용하는 거다. 

TIL

• 그리디 알고리즘