[자바/그리디] 코드트리. 최대 숫자 만들기

문제

문제 링크

해석

그리디는 "언제나 최선"인 경우라는 기준이 존재하여, 그 기준을 바탕으로 차례대로 선택하는 것이 가능할 때, 정렬이나 특정 연산을 통해 전체 연산을 최적화하는 알고리즘이다.

 

이 문제는 그리디 알고리즘 개념학습 마지막 문제이며, 이를 해결하기 위해서는 직관적으로 알 수 있듯 "가장 앞의 숫자가 큰 숫자를 먼저 고른다." 가 첫 번째 기준이 되어야 한다. 그리고 두 번째 조건이 중요한데, "가장 앞자리의 숫자가 동일할 경우, 두 세 번째 숫자도 체크해야 한다."는 게 고려되어야 한다. 즉, 결국 모든 숫자를 체크해야만 할 것 같은 느낌이 든다.

하지만 이를 잘 생각해보면, 일단 앞 자리 기준으로 큰 숫자를 먼저 앞으로 배치하되, 만약 앞자리가 같다면 직접 붙여봐서 더 큰 경우가 될 때의 앞에 붙인 숫자가 먼저 나오기만 하면 되는 거라고 이해할 수 있다. 이를 pseudo code로 표현하면 다음과 같다.

Arrays.sort(arr, new Comparator<>() {
    @Override
    public int compare(Integer i1, Integer i2) {
        if    (첫 번째 자리가 동일하다면) {
            String s1 = "" + i1 + i2;
            String s2 = "" + i2 + i1;
            return s2.compare(s1);
        }
        return i2의 첫 번째 자리수 - i1의 첫 번째 자리수
    }
});

 

사실 위 논리대로 해도 문제는 풀 수 있을 것이다. 근데 코드가 복잡하니 조금 더 단순화하자면, 결국 언제나 둘을 직접 붙여봤을 때 더 크게 되는 숫자가 먼저 나오도록 정렬하면 정답을 구할 수 있을 것으로 이해할 수 있다. 따라서 정렬 기준만 똑바로 하면 그리디로 이 문제를 풀 수 있다.

 

+++ 레슨런 있음

코드

아래 코드를 제출하니까 시간이 1000ms가 넘게 걸리는 걸 확인할 수 있었다. 자바가 JVM을 로드해야 해서 느리다 하더라도 단순한 로직에서조차 1000ms가 초과되는 걸 보니 뭔가 비효율적으로 돌아가고 있는 것으로 이해할 수 있었다. 어떤 부분에서 비효율이 있는지는 아래에서 설명하겠다.

public class Main {
    /**
    * 수행시간 : 1624 ms
    *
    * 메모리 : 154 KB
    *
    * 시간복잡도 : O(N * logN) // N개의 element에 대하여 정렬을 수행하는 시간복잡도가 O(N * logN)
    */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        String ans = solution(arr);

        bw.write(ans);
        br.close();
        bw.flush();
        bw.close();
    }

    private static String solution(Integer[] arr) {
        Arrays.sort(arr, (o1, o2) -> {
            String s1 = Integer.toString(o1) + Integer.toString(o2);
            String s2 = Integer.toString(o2) + Integer.toString(o1);
            return s2.compareTo(s1);
        });

        StringBuffer sb = new StringBuffer();
        for (Integer i : arr) {
            sb.append(i);
        }

        return sb.toString();
    }

}

 

위 로직이 겉으로 보기엔 멀쩡해 보여도 곰곰히 생각해보면, 위 로직에서는 "Integer으로 입력받음 -> String으로 변환하여 숫자 생성 및 비교하여 정렬 -> 정렬된 Integer 배열을 순회하여 문자열로 합성 -> 출력" 으로 구성되어 있다. 즉, 불필요한 형변환을 수행하여 연산시간 누수가 발생하고 있는 것이다.

 

따라서 아래와 같이 변경할 수 있다. 문자열로 바로 받아서 그대로 compare메서드를 이용하여 비교 연산을 하고 그대로 합성해서 출력하면 된다. 이렇게 하니까 시간이 2배 이상 줄어들었다! 메모리도 3배 가량 최적화되었다.

package 알고리즘연습.codetree.그리디;

import java.util.*;
import java.io.*;

public class Main {
    /**
    * 시간복잡도 : O(N * logN)
    *
    * 실행 시간 : 617 ms
    *
    * 메모리 : 53 MB
    */
    public static ArrayList<String> inputList = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        String[] arr = new String[n];

        for(int i = 0 ; i < n ; i++){
            arr[i] = br.readLine();
        }

        String ans = solution(arr);

        bw.write(ans);
        br.close();
        bw.flush();
        bw.close();
    }

    private static String solution(String[] arr) {
        Arrays.sort(arr, (s1, s2) -> {
            String ss1 = s1 + s2;
            String ss2 = s2 + s1;

            return ss2.compareTo(ss1);
        });

        StringBuffer sb = new StringBuffer();
        for (String s : arr) {
            sb.append(s);
        }

        return sb.toString();
    }
}

레슨런

Numeric 데이터를 입력받는 경우에 너무나 당연하게 Integer.parseInt()를 이용하여 입력을 받곤 했다. 자동반사적인 습관이 되어 있는 것이다. 하지만 이렇게 숫자 타입 변수로 파싱하는 연산 자체가 무거운 연산인데, 이를 기껏 해두고 결국 나중에 다시 문자열로 가공하는 로직을 내 손으로 구성했음을 깨달았을 때에는 아차 싶었다. 숲을 보지 못하고 나무 나무 하나하나만 고려한 설계였다.

 

앞으로는 로직 구성에 있어서 전체를 한번 체크할 수 있도록 연습해 봐야겠다.