[프로그래머스/java] 가장 큰 수 - Arrays.sort Comparator Override

가장 큰 수

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

이 문제를 풀 때, 제일 먼저 생각했던 풀이 방법이 백트래킹(완전탐색) 이었다.

 

큰 고민 없이 주어진 배열에서 모든 수를 조합해서 도출해낼 수 있는 쉬운 결론이었다.

 

MaximumNumber.java

package maximumNumber;

import java.util.Arrays;
import java.util.Comparator;

public class MaximumNumber {
	public static void main(String[] args) {
		Solution s = new Solution();
		int[] arr1 = {6, 10, 2};
		System.out.println(s.solution(arr1));
		int[] arr2 = {3, 30, 34, 5, 9};
		System.out.println(s.solution(arr2));
	}
}

class Solution {
	boolean[] check;
	int max;
	String maxStr;
	
    public String solution(int[] numbers) {
        String answer = "";
        
        check = new boolean[numbers.length];
        max = Integer.MIN_VALUE;
        maxStr = "";
        
        find(numbers, 0, 0, "");
        answer = maxStr;
        
        return answer;
    }
    
    public void find(int[] numbers, int idx, int cnt, String str) {
    	if(cnt == numbers.length) {
    		max = Math.max(max, Integer.parseInt(str));
    		maxStr = Integer.toString(max);
    		return;
    	} 
    	
    	for (int i = 0; i < numbers.length; i++) {
			if(!check[i]) {
				check[i] = true;
				find(numbers, i+1, cnt+1, str + numbers[i]);
				check[i] = false;
			}
		}
    }
}

 

테스트케이스는 모두 통과했지만,

 

제출 결과는 처참했다.....

 

가장 큰 수 백트래킹 결과

 

어떻게 풀어야할 지 잘 모르겠어서 https://velog.io/@qodlstjd12/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%88%98를 참고했다.

 

참고해보니, Array.sort를 Comparator로 Override해서 풀면 되는 문제였다.

 

처음에 문자열 배열에 int형 배열에 있는 수를 초기화해주고,

 

이제 배열의 요소들끼리 비교해주면 되는 문제였다.

 

Arrays.sort 내부의 Comparator에서 

 

오름차순의 배열  str = o1 + o2 과

내림차순의 배열 reverse = o2 + o1을 서로 비교하여

 

문자열을 첫글자를 확인하여 내림차순으로 정렬하고, 

 

문자열의 그 다음 순번의 인덱스에 해당하는 문자값을 비교하여 

 

더 큰 값을 앞 순서로 배치해주는 로직으로 문제를 해결한다.

 

그리고, 모든 요소가 0일 수 있으므로 0에 대한 예외처리를 해준다. ( if(zero) answer = "0"; )

 

MaximumNumber.java

package maximumNumber;

import java.util.Arrays;
import java.util.Comparator;

public class MaximumNumber {
	public static void main(String[] args) {
		Solution s = new Solution();
		int[] arr1 = {6, 10, 2};
		System.out.println(s.solution(arr1));
		int[] arr2 = {3, 30, 34, 5, 9};
		System.out.println(s.solution(arr2));
	}
}

class Solution {
	String[] numStr;
	
    public String solution(int[] numbers) {
        String answer = "";
        
        numStr = new String[numbers.length];
        boolean zero = true;
        
        for (int i = 0; i < numStr.length; i++) {
			numStr[i] = Integer.toString(numbers[i]);
			if(numbers[i] != 0) zero = false;
		}
        
        Arrays.sort(numStr, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				String str = o1 + o2, reverse = o2 + o1;
				return reverse.compareTo(str);
			}
		});
        
        for (int i = 0; i < numStr.length; i++) {
			answer += numStr[i];
		}
        
        if(zero) answer = "0";
        
        return answer;
    }
}

 

제출 결과