[LV.2][JAVA] 가장 큰 수

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

프로그래머스

푸는 동안 사고과정 및 개선점

import java.util.*;

class Solution {
    static boolean[] v; 
    static String[] out;
    static int n;
    static TreeSet<String> pq = new TreeSet<String>(Collections.reverseOrder());
    
    public static void perm(int[] num, int depth){
        if(depth == n){
            StringBuilder sb = new StringBuilder();
            for(String item: out){
                sb.append(item);
            }
            pq.add(sb.toString());
            return;
        }
        for(int i=0; i<num.length; i++){
            if(!v[i]){
                //방문하지 않았으면 다음위치에 넣기
                v[i] = true;
                out[depth] = Integer.toString(num[i]);
                perm(num, depth+1);
                v[i] = false;
            }
        }
    }
    public String solution(int[] numbers) {
        String answer = "";
        // 순열로 일단 만들 수 있는 모든 경우의수를 만들어서, PriorityQueue에 넣기
        n = numbers.length;
        v = new boolean[n];
        out = new String[n];
        perm(numbers, 0);
        
        answer = String.valueOf(pq.first());
        return answer;
    }
}

처음에는 순열로 접근하면 될 줄 알았다. TreeSet을 사용하기 전에는 우선순위 큐를 써서 만들었다. 근데 input을 보면

numbers 길이가 100000인데, 이러면 순열생성 시간복잡도가 n!라서 무조건 시간초과, 메모리 초과가 발생한다.

 

방법을 바꿔야된다. 

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] strNumbers = new String[numbers.length];
        
        for(int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }
        
        Arrays.sort(strNumbers, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return (b + a).compareTo(a + b);
            }
        });
        
        if(strNumbers[0].equals("0")) return "0";
        
        StringBuilder answer = new StringBuilder();
        for(String s : strNumbers) {
            answer.append(s);
        }
        
        return answer.toString();
    }
}

String으로 다 바꾼다음, Comparator를 새로 정의하는 방식을 사용했다. 이런 문제를 몇번 풀었는데 이렇게 하는 건 처음이다...

---

# 추가 공부

`Arrays.sort(arr, new Comparator<T>(){ })`

Arrays.sort(strNumbers, new Comparator<String>() {
    @Override
    public int compare(String a, String b) {
        return (b + a).compareTo(a + b);
    }
});

오랜만에 Comparator를 사용하니까 진짜 생각이 안났다.

Arrays는 배열을 파라미터로 받아서 처리하는데, 안쓰면 계속 까먹어서 일단 적어둔다. 같을 때(기존 순서 유지), 작을 때(-1), 클 때(1)를 각각 기준으로 두고 정렬 순서를 결정한다.

 

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!