[프로그래머스]가장 큰 수(Level2)

📝문제 링크

프로그래머스 > 정렬 > 가장 큰 수 문제보기

🔑문제 KeyPoint

단순한 순열문제라고 생각하여, DFS를 이용하여 문제를 풀었다.😂
이렇게 풀면 예제는 다 맞아도, 실행하면 시간초과 메모리초과가 나온다.▶DFS로 풀이한 순열

'정렬' 카테고리에 속해 있으니, 정렬을 이용하여 문제에 접근해보았다.
우선, numbers[]를 이용하여 정렬을 해야하는데, 예제2로 보면 30과 9를 정렬하려면 숫자 맨 첫번째 자리만 가지고 정렬을 해야 가장 큰 수를 찾을 수 있다.

숫자가 아닌 문자로 정렬 후 문자열을 붙이면 정답일거라고 생각했다.

String[] strs ; // numbers를 문자로 변환한 String 배열 (과정 생략)
Arrays.sort(strs, new Comparator<String>() {
	@Override
	public int compare(String s1, String s2) {
		return ((s2).compareTo(s1));
	}
});

// lamda식으로 표현하면 아래처럼 표현가능
Arrays.sort(strs , (s1, s2 ) -> (s2).compareTo(s1));

근데 이렇게 풀이하면, 9, 5, 34, 3, 30이 아닌 9, 5, 34, 30, 3순으로 결과가 나온다.(Level2라면서,,,,😭😭😭)

결국 구팀장을 이용해 검색하여 힌트를 얻었다.

💡각 숫자들을 합친 문자열을 가지고 비교를 해야한다.
3과 30을 합쳐서 330이 큰지 303 비교하여 정렬하는 문제이다.

⚒ 예외케이스는 0이 여러번 나오는 경우이다. (다른 숫자가 여러번 나오는 경우는 상관 X)

결과적으로 나오는 답은 매우 단순하지만, 답까지 생각을 도출하는게 쉽지는 않은 문제같다.

💻문제 풀이

public String solution(int[] numbers) {
	String answer = "";
	int len = numbers.length;
	// 1. int형 배열을 String배열로 변환
	String[] strs = new String[len];
	for(int i=0;i<len;i++){
		strs[i] = Integer.toString(numbers[i]);
	}

	// 2. String 으로 정렬한다. (s1 + s2) , (s2 + s1)를 비교했을때 사전적으로 더 큰 순으로 정렬
	Arrays.sort(strs, new Comparator<String>() {
		@Override
		public int compare(String s1, String s2) {
			return ((s2+s1).compareTo(s1+s2));
		}
	});

	// 예외케이스
	// 모두 0 인 경우
	if("0".equals(strs[0])){
		return "0";
	}
	for(String st : strs){
		answer += st;
	}
	return answer;
}

전체 소스보기(git)

[참조]

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