[백준 Java] 2812 크게만들기 그리디 알고리즘

[링크]

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

[문제풀이 방법]

가장 큰 숫자를 만들기 위해서는 앞자리가 가장 큰 숫자가 나와야 한다.

따라서 앞자리의 제일 큰 숫자가 오도록 숫자를 찾으면 된다 

하지만 문제는 N개중 K개를 지우는 경우이므로 

앞에서부터 k까지만 탐색을 해야 뒤에 남은 자리의 숫자를 모두 채울 수 있다 

 

예를 들어 123456의 6자리 숫자에서 4자리를 지우는 경우에는 (0~4범위 [1,2,3,4,5])범위 안에서 탐색하여 5를 선택하고

하나를 선택하였으므로 탐색 가능 범위가 (6~6범위 [6])까지 탐색 가능하여 그다음에 6을 선택해야 한다.

 

그래서 일단 모든 숫자는 이전 선택된 값 이후로 탐색해야 함으로  point를 두고 그 이후만 탐색하는 방식으로 구현하였다.

max의 기본값은 탐색 범위내 arr[point] 즉, 0자리를 기준으로 해두고 max 값을 탐색하였다. 

max가 9인 경우는 가장 큰숫자여서 더 이상의 탐색이 필요 없으므로 바로 브레이크하고 빠져나오도록 하였다.

이후에 max 값을 정답에 저장하고, 방금 저장한 max 값 이후로 다음 선택 가능한 범위 이므로 point를 maxIdx+1로 설정해주며 끝까지 진행하였다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] arr = Stream.of(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

        int point = 0;
        while (sb.length() < N - K) {
            int max = arr[point];
            int maxIdx = point;
            //일단 최댓값 찾기(뒤에를 나머지 채워야 할 수로 남겨두고)
            for (int i = point; i <= K + sb.length(); i++) {
                if (max < arr[i]) {
                    max = arr[i];
                    maxIdx = i;
                }
                if (max == 9) break;
            }
            sb.append(max);
            point = maxIdx + 1;
        }
        System.out.println(sb);

    }
}