프로그래머스 (Level 3) - 가장 큰 수

문제 설명

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

 

풀이

처음에는 완전 탐색 알고리즘을 이용해 모든 수의 조합을 탐색한 후 가장 큰 수를 찾으려고 했다. 하지만 코드를 제출했을 때 메모리 초과가 나는 것을 확인하고, 다른 풀이를 모색하였다.

 

정수형 배열 numbers를 문자열 배열로 변환한다. 문자열 배열을 특정 기준으로 정렬해주기 위해서 Comparator 인터페이스 내 compare( ) 메서드를 재정의해주어야 한다.

 

예제 2의 경우 3, 30 두 개의 숫자가 있을 때 3+30=330, 30+3=303을 비교해보면 330이 더 크기 때문에 숫자 3이 숫자 30보다 앞에 나와야 한다. 이러한 규칙으로 compare( ) 메서드를 재정의한 후 답을 구하면 되는 문제이다.

 

전체 소스코드

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

public class Solution08 {
	public String solution(int[] numbers) {
		String[] strings = new String[numbers.length];

		for (int i = 0; i < strings.length; i++) {
			strings[i] = Integer.toString(numbers[i]);
		}

		Arrays.sort(strings, new Comparator<String>() {

			@Override
			public int compare(String o1, String o2) {

				return (o2 + o1).compareTo(o1 + o2);
			}
		});

		if (strings[0].equals("0"))
			return "0";

		String answer = "";

		for (String string : strings)
			answer += string;

		return answer;
	}
}