🎯1주차A "가장 큰 수"

문제설명

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

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

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

제한 사항

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

입출력 예

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

✍내 코드

import java.util.ArrayList;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        ArrayList<String> list = new ArrayList<String>();
        
        for(int i=0; i<numbers.length; i++) {
        	String str = "";
        	for(int j=0; j<3; j++) {
        		str += String.valueOf(numbers[i]);
        	}
    		list.add(str); // int를 String으로 형변환
        }
        
        list.sort(Comparator.reverseOrder()); // 내림차순
        
        for(String num : list) {
        	answer += num.substring(0, num.length()/3);
        }
        if(answer.charAt(0) == '0') answer = "0";
        return answer;
    }
}

✏️모든 수를 문자열로 바꾼 뒤 내림차순으로 정렬
✏️30, 3은 303보다 330이 더 크다 => 순서가 바르게 나올 수 없을 수 있다.
✏️numbers의 원소는 최대 1000이므로 길이를 3배로 늘려서 비교해준다. => 303030과 333의 문자열 비교는 333이 더 크다!

강의내용

✔️세 자리 수 10개만 모여도 총 30자리 수가 되어버림 -> Integer, Long의 범위가 훨씬 넘을 수 있다.
✔️숫자로 생각하면 어려움이 있기 때문에 반환 타입인 문자열을 생각해서 문자열로 다루면 좀 더 자연스럽게 접근이 가능하다.
✔️숫자로 정렬하게 되면 6, 10, 2 와 같이 되는데 가장 큰 조합의 경우는 6, 2, 10이다.
✔️따라서, 숫자 -> 문자 -> 내림차순 정렬 -> 조합 하도록 한다.

💡 Tip.
Java 언어를 사용한다 == Java가 제공하는 기본 라이브러리를 사용한다.
기본 라이브러리인 java.lang.과 java.util. 사용법을 숙지한다.

✍🏻정답 코드1

public String solution(int[] numbers) {
	// 숫자 -> 문자 -> 내림차순 정렬 -> 조합
	String[] strNums = new String[numbers.length];
    	for(int i=0; i<numbers.length; i++) {
		strNums[i] = "" + numbers[i];
	}

	// 내림차순 정렬 => 좀 더 효율적으로 사용
	Arrays.sort(strNums, new Comparator<String>() {
		public int compare(String s1, String s2) {
			return (s2+s1).compareTo(s1+s2);
		}
	});
    
    	//버블소트 정렬
        for(int i=0; i<strNums.length; 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) { // 왼 < 오
                        	strNums[i] = strNums[j];
                            	strNums[j] = s1;
                       	}
                }
	}


	// 만약 모든 숫자가 0이라면 그냥 0 출력
	if(answer.charAt(0) == '0') return "0";
        return answer;
}

✔️버블소트 말고 자바 라이브러리 사용

// 내림차순 정렬 => 좀 더 효율적으로 사용 -> 코드 간결화
// Java 8 이상부터 람다 사용 가능
// 어차피 comparator 인터페이스 안에 comparator 메소드 하나만 존재, compare도 하나만 존재 => 생략해도 컴파일러가 알아서 인식가능
Arrays.sort(strNums, (s1, s2) -> (s2+s1).compareTo(s1+s2));

// 내림차순 정렬 => 좀 더 효율적으로 사용
Arrays.sort(strNums, new Comparator<String>() {
	public int compare(String s1, String s2) {
	return (s2+s1).compareTo(s1+s2);
	}
});

✔️startsWith() 사용

// 좀더 권장되는 방식
if(answer.startsWith("0")) return "0";

✍🏻정답 코드2

import java.util.stream.*;

public String solution(int[] numbers) {
//	IntStream.of(numbers).mapToObj(n -> String.valueOf(n))
	IntStream.of(numbers)
    		.mapToObj(String::valueOf)
    		.sorted((s1, s2) -> (s2+s1).compareTo(s1+s2))
    		.collect(Collectors.joining());


	// 만약 모든 숫자가 0이라면 그냥 0 출력
	// 좀더 권장되는 방식
    	if(answer.startsWith("0")) return "0";
        return answer;
}

💡stream 라이브러리를 사용하면 좀 더 코드를 간편화 할 수 있다. wow,,,🙀