[프로그래머스 알고리즘] 가장 큰 수

Heejun Kwon·2021년 6월 27일

Java 알고리즘 정렬 프로그래머스

알고리즘 풀이

목록 보기

10/11

프로그래머스 연습문제
프로그래머스 레벨2 - 가장 큰 수

🔎 문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

🚫 제한조건

numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

💻 입출력 예

📄🤔 코드 및 풀이과정

🔹 1번

public static String solution(int[] numbers) {
        
	String answer = "";
        
	String[] strNum = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
		strNum[i] = String.valueOf(numbers[i]);
	}
        
        String temp;
        String forward = "";
        String reverse = "";
	for (int i = 0; i < strNum.length-1; i++) {
		for (int k = i+1; k < strNum.length; k++) {
			forward = strNum[i] + strNum[k];
			reverse = strNum[k] + strNum[i];
			if(reverse.compareTo(forward) > 0) {
				temp = strNum[i];
				strNum[i] = strNum[k];
				strNum[k] = temp;
			}				
		}//inFor
	}//outFor
		
	for (String s : strNum) {
		answer += s;
	}
		
	return (answer.substring(0, 1).equals("0"))? "0" : answer;
}

🔸 1번 풀이

처음 코드는
정말 단순한 방법으로
1번째 문자열 + 2번째 문자열 과 2번째 문자열 + 1번째 문자열을
compareTo로 비교해서, 2번째 문자열 + 1번째 문자열이 더 클 경우
2번째 문자열을 1번째 문자열과 교환하는 방식을 선택했다.

그 뒤에 배열을 문자열로 만들고
배열에 0만 여러개가 존재했을 경우 000, 00000 이런 결과가 나올 수 있기에
시작이 0인 경우 0을 리턴, 아니면 그대로 배열로 만든 문자열을 리턴했다.

테스트 케이스 11개 중에 6개를 통과하고
5개는 시간 초과로 실패했다.

이 코드를 짜기 전에는 중첩 반복문을 사용하지 않기 위해
문자열의 정렬 특징을 활용하여 문자열이 든 배열을
Arrays.sort(strNum, Collections.reverseOrder());
를 통해서 내림차순으로 정렬한 뒤에
1번째 문자열과 2번째 문자열을 합친 값을 compareTo로 비교
2번째 문자열과 3번째 문자열을 합친 값을 compareTo로 비교
3번째 문자열과 4번째 문자열을 합친 값을 comapreTo로 비교 하는 등
(n번째 문자열 + n+1번째 문자열).compareTo((n+1번째 문자열 + n번째 문자열))
을 비교하는 방식을 사용하려 했는데
sort시 단순하게 내림차순으로 정렬할 경우
{2, 20, 220}이 {2, 220, 20}으로 정렬되어야 하는데
{220, 2, 20}으로 정렬되는 등 정상적인 답이 나오지 않았다.

그래서 어쩔 수 없이 중첩 반복문을 사용해서 풀어봤는데
시간초과로 통과되지 않아서 다시 Arrays.sort를 활용하되
위에서 말한 문제가 발생하지 않는 방법을 찾아보았다.

🔹 2번

public static String solution(int[] numbers) {
    
	String answer = "";
	String[] strNum = new String[numbers.length];
    	for (int i = 0; i < numbers.length; i++) {
		strNum[i] = String.valueOf(numbers[i]);
	}
       
	Arrays.sort(strNum, new Comparator<String>() {
		@Override
		public int compare(String o1, String o2) {
        		return (o2 + o1).compareTo(o1 + o2);
                }        	
	});

	for (String s : strNum) {
		answer += s;
	}        
	
	return answer.startsWith("0") ? "0": answer;
}

🔸 2번 풀이

1번 코드에서 계속 고민하며 여러가지를 생각해보면서
sort 메서드의 매개변수 목록을 보고 있다가 Comparator가 눈에 들어왔다.

정렬시 비교측정기인 Comparator을 사용하여 정렬 기준을 변경할 수 있는데
분명 한 번 배웠던 것임에도 바로 떠올리지 못한 점이 매우 아쉬웠다.

Arrays.sort로 문자열 배열을 정렬하되
익명클래스를 활용해 비교측정기를 만들고,
compare를 오버라이딩해서 비교하는 두 문자열을
(문자열2 + 문자열1).compareTo(문자열1 + 문자열2)로 비교해서
정렬되도록 하여 문제를 통과했다.

익명 클래스 역시 배운 내용임에도 처음에 기억이 나지 않아
측정기 클래스를 만들고, 생성자로 비교측정기 객체를 만들까 생각했었다.
그러다가 인터넷에서 Comparator를 다시 공부해보면서
객체를 생성할 때 익명 클래스를 활용하는 예제들을 보고
이럴 때 사용하는구나! 하면서 바로 사용해보았다.