[프로그래머스 - 정렬] 02. 가장 큰 수

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 합니다.

입출력 예numbersreturn

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

---

문제 해결 과정

1. 숫자를 문자로 바꾸기
2. 내림차순 정렬
3. 조합

 

정렬하는 방법

1. 버블 소트로 직접 구현
2. 소트 함수로 구현
3. 람다식으로 구현

숫자가 성립되지 않는 경우 예외처리

1. str.charAt(0) == '0'
2. str.startsWith("0")

 

1. 버블 소트로 직접 구현

package algo1;

public class OneWeek02 {
	public static void main(String[] args) {
		
	}
	static String solution(int[] numbers) {
		//숫자 -> 문자 -> 내림차순정렬 -> 조합
		//1. 문자배열로
		String [] strNums = new String[numbers.length];
		for(int i=0;i<numbers.length;i++) {
			strNums[i]=""+numbers[i];
		}
		//2. s1+s2와 s2+s1 비교해 내림차순정렬
		for(int i=0;i<strNums.length-1;i++) {
			for(int j=i+1; j<strNums.length;j++) {
				String s1=strNums[i];
				String s2=strNums[j];
				if((s1+s2).compareTo(s2+s1)<0) {
					//303이 330보다 작을때 -> 오른쪽이 더 클경우에
					strNums[i]=strNums[j];
					strNums[j]=s1;
					//교환
				}
			}
		}
		 String answer="";
		 for(String s : strNums) {
			 answer+=s;
		 }
		 //맨 앞 숫자가 0이면 0을 리턴
		 if(answer.charAt(0)=='0') return "0";
		 
		 return answer;
	}

}

 

2. 소트 함수로 구현

package algo1;

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

public class OneWeek02_R {
	//효율성 테스트
	//-> 정확성 테스트에서 시간초과 발생
	//: 루프에서 무한루프가 돌 경우, 제한시간보다 오래걸릴경우
	
	// 버블 소트를 사용했기때문에 느리다?
	//-> 라이브러리 사용하자
	public static void main(String[] args) {
		int[] numbers= {3, 30, 34, 5, 9};
		System.out.println(solution(numbers));
	}
	static String solution(int[] numbers) {
		//숫자 -> 문자 -> 내림차순정렬 -> 조합
		//1. 문자배열로
		String [] strNums = new String[numbers.length];
		for(int i=0;i<numbers.length;i++) {
			strNums[i]=""+numbers[i];
		}
		//#1. 소트 함수로 변경
		//-> s1+s2와 s2+s1 비교해 내림차순정렬
		Arrays.sort(strNums, new Comparator<String>() {
			public int compare(String s1, String s2) {
				//return (s1+s2).compareTo(s2+s1);
				//오름차순 정렬
				return (s2+s1).compareTo(s1+s2);
				//내림차순 정렬
			}
		});
		String answer="";
		 for(String s : strNums) {
			 answer+=s;
		 }
		 
		 //#2. 문자열 시작으로 변경
		//맨 앞 숫자가 0이면 0을 리턴
		 if(answer.startsWith("0")) return "0";
		 
		 return answer;
	}

}

 

3. 람다식으로 구현

package algo1;

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

public class OneWeek02_R {
	//효율성 테스트
	//-> 정확성 테스트에서 시간초과 발생
	//: 루프에서 무한루프가 돌 경우, 제한시간보다 오래걸릴경우
	
	// 버블 소트를 사용했기때문에 느리다?
	//-> 라이브러리 사용하자
	public static void main(String[] args) {
		int[] numbers= {3, 30, 34, 5, 9};
		System.out.println(solution(numbers));
	}
	static String solution(int[] numbers) {
		//숫자 -> 문자 -> 내림차순정렬 -> 조합
		//1. 문자배열로
		String [] strNums = new String[numbers.length];
		for(int i=0;i<numbers.length;i++) {
			strNums[i]=""+numbers[i];
		}
		
		//#1. 람다식으로 변경
		//-> s1+s2와 s2+s1 비교해 내림차순정렬
		Arrays.sort(strNums, (s1,s2) -> (s2+s1).compareTo(s1+s2));
		
		 String answer="";
		 for(String s : strNums) {
			 answer+=s;
		 }
		 
		 //#2. 문자열 시작으로 변경
		//맨 앞 숫자가 0이면 0을 리턴
		 if(answer.startsWith("0")) return "0";
		 
		 return answer;
	}

}

 

+) 세련된 풀이 - 스트림 이용

package algo1;

import java.util.stream.*;

public class OneWeek02_Stream {
	//효율성 테스트
	//-> 정확성 테스트에서 시간초과 발생
	//: 루프에서 무한루프가 돌 경우, 제한시간보다 오래걸릴경우
	
	// 버블 소트를 사용했기때문에 느리다?
	//-> 라이브러리 사용하자
	public static void main(String[] args) {
		int[] numbers= {3, 30, 34, 5, 9};
		System.out.println(solution(numbers));
	}
	static String solution(int[] numbers) {
		//숫자 -> 문자 -> 내림차순정렬 -> 조합
		//1. 문자배열로
		//IntStream.of(numbers).mapToObj(n->String.valueOf(n));
		//문자배열로 변환 후 소트후 합치기
	String answer=
		IntStream.of(numbers).mapToObj(String::valueOf)
		.sorted((s1,s2)->(s2+s1).compareTo(s1+s2))
		.collect(Collectors.joining());
		 
		 //#3. 문자열 시작으로 변경
		//맨 앞 숫자가 0이면 0을 리턴
		 if(answer.startsWith("0")) return "0";
		 
		 return answer;
	}

}