[코딩테스트 #11] 가장 큰 수

문제 설명

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"

💡문제 해결💡

1. 쫙 정렬해서 문자열로 싹 붙이자
2. 그냥 정렬은 붙였을 경우 는 고려되지 않기 때문에 정렬 기준을 새로 만든다
3. Comparator의 제네릭 타입을 String으로 한 후 앞 뒤 String을 붙인 값을 비교 오름차순이기 때문에 (큰 수가 왼쪽으로 가야 붙였을 때 전체적으로 큰 값)
   -1을 곱하거나 비교 순서 바꿈
4. stream을 사용해서 int 배열을 String 배열로 바꾼다
5. stream을 사용해서 만든 정렬기준으로 정렬하고 collect(Collectors.joining()) 사용해서 문자열로 바꿈

주의
6. 0, 0, 0 ..의 배열일 경우 리턴 값이 00000...일 것,
시작 값이 0일 경우 또는 cahrAt(0)이 0일 경우 "0"을 반환

버전1

import java.util.Arrays;
import java.util.stream.*;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] numStr = Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                .toArray(String[]::new);
        
        Com c = new Com();
        
        answer = Arrays.stream(numStr).sorted(c).collect(Collectors.joining());
        
        return answer.startsWith("0") ? "0" : answer;
    }
}

class Com implements Comparator<String>{
    
    @Override
    public int compare(String s1, String s2){
        return (s1 + s2).compareTo(s2 + s1) * -1;
    }
}

버전2

• 비교 기준을 함수형 인터페이스 구현으로 전달

import java.util.Arrays;
import java.util.stream.*;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] numStr = Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                .toArray(String[]::new);
        
        answer = Arrays.stream(numStr).sorted(new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                return (s1 + s2).compareTo(s2 + s1) * -1;
            }
        }).collect(Collectors.joining());
        
        return answer.startsWith("0") ? "0" : answer;
    }
}

버전 3

• Comparator 구현 대신 람다식으로 전달

import java.util.Arrays;
import java.util.stream.*;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] numStr = Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                .toArray(String[]::new);

        answer = Arrays.stream(numStr).sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2)).collect(Collectors.joining());
        
        return answer.startsWith("0") ? "0" : answer;
    }
}

버전 4

• Stream 부분 합침

import java.util.Arrays;
import java.util.stream.*;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        StringBuilder sb = new StringBuilder();
        Arrays.stream(numbers)
            .mapToObj(String::valueOf)
            .sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))
            .forEach(a -> sb.append(a));
        
        answer = sb.toString();
        
        return answer.startsWith("0") ? "0" : answer;
    }
}

버전 5

• Arrays.toString이용해서 배열을 문자열로 만들고 replace 이용해서 연속된 한 줄의 문자열로 만들기
• 정규식 이용해서 0으로 시작하면 "0" 반환하게 변환해보기

import java.util.Arrays;
import java.util.stream.*;
import java.util.Comparator;


class Solution {
    public String solution(int[] numbers) {
        
        String answer = Arrays.toString(Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                .sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))
                .toArray())
                .replace(", ", "")
                .replace("]", "")
                .replace("[", "");
        
        return answer.startsWith("0") ? "0" : answer;
    }
}