[프로그래머스] Lv.2 : 큰 수 만들기 - 자바[Java]

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

프로그래머스

풀이

그리디 알고리즘을 사용하기 위해서는 아래와 같이 2가지 조건을 만족해야 한다.

1) 탐욕 선택 속성(Greedy Choice Property)
2) 최적 부분 구조(Optimal Substructure)

1)은 이전의 선택이 이후에 영향을 주지 않음을 의미하며, 2)는 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다는 것이다.

	1개 제거	2개 제거	3개 제거	4개 제거
1924	924	94	9
1231234	231234	31234	3234	334

 

위의 입출력 예시를 보면, 앞에서부터 각 자리 숫자를 탐색하여 뒤에 있는 숫자보다 작은 경우에 해당 숫자를 삭제한다.

각 선택마다 이전의 선택이 이후에 영향을 주지 않으며, 부분 문제의 최적결과가 전체에도 그대로 적용되기 때문에 그리디 알고리즘의 조건을 만족한다.

 

코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder(number);
        
        while (k-- > 0) {
            int i = 0;
            int size = answer.length();
            
            for (; i < size - 1; i++) {
                if (answer.charAt(i) < answer.charAt(i+1)) { // 뒤에 나올 숫자보다 작으면 제거
                    answer.deleteCharAt(i);
                    break;
                }
            }
            
            if (i == size - 1) { // 맨 끝의 숫자 제거
                answer.deleteCharAt(i);
            }
        }
        
        return answer.toString();
    }
}

 

그리디 관련 참고 글

알고리즘 - 그리디 알고리즘(Greedy Algorithm)

[알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java)