[Algorithm] 그리디 알고리즘

Greedy Algorithm

현재 상태에서 최선의 선택지를 계속해서 고르다보면, 전체적으로도 최선의 선택지가 된다.

실제로는 최선의 결과가 나올 때가 있고, 안나올 때가 있다.

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1번부터 다시 반복.

 

프로그래머스 큰 수 만들기

아래 코드는 앞에서부터 k 범위 내의 최대값을 순차적으로 골라서 새로운 배열에 추가하는 방법이다. 

그 순간의 최선의 선택인 최대값을 골라 가장 큰 결과값을 도출하였다.

class Solution {
   public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        int max = 0;
        for(int i=0; i<number.length() - k; i++) {
            max = 0;
            for(int j = index; j<= k+i; j++) {
                if(max < number.charAt(j)-'0') {
                    max = number.charAt(j)-'0';
                    index = j+1;
                }
            }
            sb.append(max);
        }
        return sb.toString();
    }
}