Java) 프로그래머스 - 가장 큰 수

July 10, 2022

문제 링크Permalink

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

배열의 모든 원소를 조합해서 숫자를 만들어봐야 하기 때문에 순열문제라고 생각했다. 그래서 순열 만드는 함수를 만들어 모든 순열을 구한 다음에 그걸 정렬해서 가장 큰 수를 리턴하는 방식으로 했다.
테스트 케이스는 통과했지만 막상 제출하니까 시간초과가 뜨면서 실패했다…ㅎ
나중에 풀이를 보니까 접근 방법 자체가 달라서 통과할 수 없는 알고리즘이었다. 순열을 구하는 메서드에서 시간초과가 발생했거나 무한루프가 돈 것으로 예상되었다.

풀이 영상을 보고 처음에 생각했던 접근방법이 틀렸다는 걸 알게 되었다.
이 문제를 시간 안에 통과하기 위한 접근법은 숫자를 -> 문자로 바꾸고 -> 내림차순으로 정렬해서 -> 문자열로 조합 이었다.
하지만 무작정 내림차순으로 정렬하면 테스트 케이스 1처럼 6, 10인 경우에는 610이 큰 수지만 단순 내림차순으로 정렬해 버린 후 조합하면 10, 6이 되어 106이라는 결과를 얻게 된다. 그렇기 때문에 두 수를 조합한 결과가 큰 순서대로 내림차순 정렬될 수 있도록 해야한다.
이를 위해 compareTo() 메서드를 사용해 정렬 대상이 되는 앞뒤 원소 두 개를 조합한 결과에 따라 내림차순 정렬이 될 수 있도록 했다.
주 언어가 자바지만 정작 코테 준비는 C++이나 파이썬으로 많이 했었기 때문에 자바의 컬렉션에 좀 약했는데 풀이 강의는 자바 사용에 대한 팁도 많이 줘서 좋았다. 이것 하나로 수강료가 아깝지 않았다.
프로그래머스 [Java/문제풀이] 코딩테스트 광탈 방지 Kit: Java편 왕추천!!

	import java.util.*;

	class Solution {
	public String solution(int[] numbers) {
	// 정수 배열 -> 문자열 배열로 변환
	String[] strNums = new String[numbers.length];
	for (int i = 0; i < numbers.length; i++) {
	strNums[i] = String.valueOf(numbers[i]);
	}

	// 내림차순으로 정렬한다.
	// 정렬 대상이 되는 두 원소를 조합한 결과, 뒤에 있는 것이 더 크다면 앞으로 와야 한다.
	Arrays.sort(strNums, (s1, s2) -> (s2 + s1).compareTo(s1 + s2));

	// 정렬된 배열을 리턴할 문자열로 만들어준다.
	String answer = "";
	for (int i = 0; i < strNums.length; i++) {
	answer += strNums[i];
	}

	// 입력값의 시작 범위가 0이기 때문에 [0,0,0]과 같은 배열이 생길 수 있다.
	// 정답 문자열이 0으로 시작한다면 0 하나만 리턴한다.
	if (answer.startsWith("0")) answer = "0";

	return answer;
	}
	}

view raw pm-62948.java hosted with ❤ by GitHub