[프로그래머스/Java] 큰 수 만들기(Greedy 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 Greedy 파트 문제 중 하나인 '큰 수 만들기'를 자바로 풀어보았다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42883#

프로그래머스

 

 

 순간순간의 최선을 찾는 Greedy 알고리즘의 특성을 이용하여, 바로 뒤 자신보다 큰 수를 방해하는 바로 뒤의 숫자보다 작은 첫 번째 숫자를 삭제하는 것을 k번 반복했다. 이때, 원래 j를 매 loop의 반복마다 1로 초기화했었는데, 딱 한 문제에서 시간초과가 발생했다. 그래서 굳이 다시 맨 처음으로 가는 게 아닌, 삭제한 바로 앞 숫자부터 다시 확인하면 되므로, 그렇게 바꿔주었다. 

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder(number);
        
        int j = 1;
        for (int i = 0; i < k; i++) {
            if (j < 1) j = 1; 
            while (j < sb.length() 
                   && sb.charAt(j-1) >= sb.charAt(j)) j++;
            sb.delete(j-1, j);
            j -= 2;
        }
        
        return sb.toString();
    }
}