[자바]백준 16496번 큰 수 만들기 [그리디,정렬][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

문제

음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

출력

리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.

입출력 예제

알고리즘 분류

• 그리디 알고리즘
• 정렬

문제 설명

문제를 이해하는 것은 크게 어렵지 않다.

리스트에 있는 수들을 조합해서 가장 큰 수를 만들면 된다.

예를 들어 1, 2, 3, 4, 5를 조합해서 만들 수 있는 가장 큰수는 54321이다.

 

단, 출력에서 보면 수는 0으로 시작하면 안 되며, 0이 정답인 경우 0 하나를 출력해야 한다.

위의 말은 리스트에 0만 있는 경우에 0을 출력하는 부분만 신경 쓰면 된다.

코드를 보면 알겠지만 리스트에 0만 있지 않는 이상 0이 앞에 올 일은 없기 때문이다.

해설(어렵지 않아요~ 읽어보면 좋아요)

이 문제는 그리디 알고리즘 보단 정렬이 더 중요하다고 생각한다.

해당 문제를 보면 대부분 아래와 같은 생각이 먼저 떠오를 거라고 생각한다.

그냥 리스트를 내림차순 정렬 후에 맨 앞자리부터 출력하면 되는 것 아닌가?

하지만 위와 같은 방식으로 생각해서 문제를 풀면 틀릴 것이다.

왜냐면 998, 99, 9 같은 경우를 생각해 보자.

만약 내림차순이라면 998,999의 값이 출력될 텐데, 가장 큰 값은 999,998이기 때문에 정답이 될 수 없다.

 

그렇다면 어떻게 풀어야 할까??

한 가지만 생각해 주면 좋다.
내 앞에 998과 99가 있다고 가정하자.
이때, 난 어떻게 99,998이 큰 값이라고 알 수 있을까?
99,998과 99,899 둘을 비교해서 99,998이 더 크다는 것을 알 수 있을 것이다.
결국 이처럼 99 + 998, 998 +99를 조합해서 99가 앞에 있어야 더 크다는 것을 알게 되는 것이다.

 

결국 내림차순 정렬 기준을 '큰 수'가 아닌 '조합해서 큰 수'를 기준으로 내림차순 하는 것이다.

 

그리고 마지막엔 맨 앞에 0이 있는지 만약 0이 있으면 리스트의 수가 0만 있으니 0을 출력하면 된다.

근데 이 0만 있는지 체크하는 방법은 자유롭게 다른 방법을 사용해도 좋을 것 같다. 

나는 다른 사람이 볼 때 쉽게 이해할 수 있는 방식이 좋다 생각한다!

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        String[] arr = new String[T];

        for (int i = 0; i < T; i++) {
            arr[i] = st.nextToken();
        }

        Arrays.sort(arr, ((x, y) -> (y + x).compareTo(x + y)));

        StringBuilder sb = new StringBuilder();
        for (String s : arr) {
            sb.append(s);
        }
        
        if (sb.charAt(0) == '0') {
            System.out.println(0);
        } else {
            System.out.println(sb);
        }
        
        br.close();
    }
}