프로그래머스_정렬_가장 큰 수 (JAVA)

문제 설명

 

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

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

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

제한 사항

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

입출력 예

 

 

 

 

어렵지는 않지만 단순하게 생각하면 틀리는 문제입니다. 일단 숫자 연산이 아니라 문자 그대로 봐야하므로 문자열로 변환하는 방법으로 접근합니다.

 

그냥 앞자리부터 뒷자리까지를 정렬 기준으로 내림차순 정렬해버리면 위 예제에서 3과 30의 경우 303이 되어버리기 때문에 틀린 답이 나오게 됩니다. 3과 32도 마찬가지입니다. 게다가 자릿수가 4자리(최대 1000)로 정해져있지만 4개 요소 기준으로 정렬 기준을 작성하는 것도 코드가 꽤 길어지기도 합니다.

 

따라서 이 문제는 정렬 기준을 잡을 때 두 숫자를 앞 뒤로 직접 붙여보고 판단하는 수밖에 없을 것 같습니다. 남는 자릿수에 일정 숫자를 채워넣는다거나 하는 방식으로 다른 기준을 몇 번 시도해봤는데 다 안되네요. ㅎㅎ

 

 

---

 

 

아래 코드와 같이 작성할 수 있습니다. String 클래스에는 문자열 간 크기(순서)를 비교해주는 compareTo() 메소드가 있어서 편하게 작성할 수 있습니다. 직접 로직을 작성해도 어렵지는 않은 메소드입니다.

 

a.compareTo(b)

- 앞에서부터 비교하다 다른 문자열이 나오면 'a-b' 순서로 해당 문자의 아스키코드 값을 뺀 결과(int)를 리턴 

 

위 메소드에서 a, b 순서로 있을 때 (b+a).compareTo(a+b) 을 했을 경우 'b+a'가 더 크다면 자리를 바꿔주면 되므로 아래와 같이 작성해주면 됩니다.

 

package pojoPrj;

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

class Solution {

	public String solution(int[] numbers) {

		// 숫자를 문자열로 변환
		String[] result = new String[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			result[i] = String.valueOf(numbers[i]);
		}

		// 정렬
		Arrays.sort(result, new Comparator<String>() {

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

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

		// 0만 여러개 있는 배열의 경우 하나의 0만 리턴
		if(result[0].equals("0")) {
			return "0";
		}
		
		String answer = "";
		// 정렬된 문자 하나로 합치기
		for (String a : result) {
			answer += a;
		}
		return answer;
	}
}

 

 

 

함정이 하나 있습니다. 저는 중복된 숫자가 없을 줄 알았는데 자세히 보면 제약 조건에 중복에 대한 말이 없습니다. 이 말은 {0, 0, 0}같이 0으로만 이루어진 배열이 있을 수도 있다는 의미입니다. 숫자가 하나라도 0 이상이 있다면 0이 가장 앞에 나올일이 없지만 모두 0이라면 "000"이 되어 틀린 답이 될 수 있기 때문에 가장 첫 배열의 값이 "0"이라면 "0"을 하나만 리턴하는 작업이 추가로 필요합니다. 이걸 안하면 11번째 테스트에서 실패로 뜨네요. 

 

 

---

 

 

다른 코드들을 보다가 람다식이 눈의 띕니다. 저는 람다식을 별로 좋아하진 않지만 오버라딩을 간략하게 할 때는 꽤 유용한 것 같습니다. 람다식은 Comparator와 같이 딱 하나의 추상 메소드만 가진 인터페이스를 구현할 때 사용할 수 있는 문법입니다.

 

* 람다식 한줄 문법

   - (매개변수) -> 명령문;  (리턴값이 있다면 자동으로 수행 결과가 리턴됨)

 

* 람다식 여러줄 문법

  - (매개변수) -> { 명령문;  명령문;  명령문; return; }

 

위에서 Comparator 로직은 한줄이므로 아래와 같이 작성할 수 있습니다.

 

		// 정렬
		Comparator<String> comp = (o1, o2) -> (o2 + o1).compareTo(o1 + o2);
		Arrays.sort(result, comp);

 

 

그리고 위 코드도 길다싶으면 아래와 같이 작성할 수도 있습니다. 아예 함수형 인터페이스가 있는 자리를 람다식으로 대신함으로써 1회용으로만 사용하는 방식입니다. 

		// 정렬
		Arrays.sort(result, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

 

 

 

* 람다식 사용 전체코드

package pojoPrj;

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

class Solution {

	public String solution(int[] numbers) {

		// 숫자를 문자열로 변환
		String[] result = new String[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			result[i] = String.valueOf(numbers[i]);
		}

		// 정렬
		Arrays.sort(result, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

		// 0만 여러개 있는 배열의 경우 하나의 0만 리턴
		if (result[0].equals("0")) {
			return "0";
		}

		String answer = "";
		// 정렬된 문자 하나로 합치기
		for (String a : result) {
			answer += a;
		}
		return answer;
	}
}