[1주차] 2. 가장 큰 수

내가 푼 코드 및 문제 설명

https://yummy0102.tistory.com/301

[정렬] Level 2 가장 큰 수 - JAVA

---

문제 해설

이 문제는 "정렬"에 해당하는 문제이다

 

접근법을 먼저 알아보자

 

얼핏보면 숫자를 구하는 문제니까 배열로 주어지는 모든 숫자들을 사용하여 만들 수 있는 모든 경우의 수를 구하고, 그 중에서 가장 큰 값을 고르면 되지 않을까? 라는 생각을 한다

사실 나도 그럼ㅋㅋㅋㅋㅋㅋ

 

근데 이렇게 하게 되면 문제점이 발생한다!

만약 숫자가 있는 배열의 길이가 커지면, 그걸로 만드는 숫자의 길이가 int, double의 범위를 훨씬 벗어나게 된다!

예를 들어 3이 10개만 붙어도 3333333333 이 되는데 숫자가 너무 커지게 되는 것이다!

따라서 배열을 숫자로 생각해서 풀면 풀기가 어려워지는 것이다!

 

문제의 함수 반환값이 String이니까 문자열로 생각하고 푼다!

 

가장 큰 수가 되려면 숫자로써 큰 수가 앞에 오는게 아니라 글자 순서가 큰 순서대로 나열해야 한다

예를 들어 6, 2, 10인 경우 각 숫자가 큰 순서대로 나열하면 "1062"가 된다

하지만 실제 큰 수는 "6210"이다

따라서 숫자를 숫자가 아닌 문자열로 보고, 글자 순서가 큰 순서대로 나열하면 된다!!

 

따라서 문제 해결 알고리즘은 아래와 같다

1. 숫자를 문자열로 변경한다
2. 변경한 문자열을 내림차순으로 정렬한다
3. 정렬한 문자열을 모두 조합하여 반환한다

 

이제 코드를 보자

먼저 그냥 알고리즘만 맞춰 풀고 효율성을 고려하지 않은 코드를 보자!

 

나쁜 코드)

public class Step3_2_bad {
    static public String solution(int[] numbers) {
        // 숫자 -> 문자 -> 내림차순 정렬 -> 조합
        String[] strNums = new String[numbers.length];

        // 문자로 변환
        for(int i=0;i< numbers.length;i++) {
            strNums[i] = "" + numbers[i];
        }

        // Bubble Sort (DESC)
        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) { // 내림차순 정렬
                        strNums[i] = strNums[j];
                        strNums[j] = s1;
                }
            }
        }

        // 모든 문자열 조합
        String answer = "";
        for(String s : strNums) {
            answer += s;
        }

        // 예외처리 -> 문자열이 0인 경우
        if(answer.charAt(0) == '0') {
            return "0";
        }
        return answer;
    }
}

이 문제를 제출하면 시간 초과가 발생한다

그 이유는 아마 정렬 부분이 버블 정렬로 된 탓일 것이다

자바를 사용해서 코테를 풀 때는 되도록 기본 라이브러리를 사용해서 푸는 것이 가장 좋다!

따라서 저 배열 부분을 Arrays.sort를 사용하여 변경하면 아래와 같다

 

 

좋은 코드)

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

public class Step3_2_good {
    static 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>() {
            @Override
            public int compare(String s1, String s2) {
                return (s2+s1).compareTo(s1+s2);
            }
        }); */
        Arrays.sort(strNums, (s1, s2) -> (s2+s1).compareTo(s1+s2));


        // 모든 문자열 조합
        String answer = "";
        for(String s : strNums) {
            answer += s;
        }

        // 예외처리 -> 문자열이 0인 경우
        //if(answer.charAt(0) == '0') {
        if(answer.startsWith("0")) {
            return "0";
        }
        return answer;
    }
}

기존 버블 정렬 부분을 Arrays.sort를 사용하여 변경했다

또한 Java 11부터는 Compartor대신 위 코드처럼 줄여서 사용이 가능하다고 한다!

 

그리고 아래 예외처리 부분에서 문자열의 첫 글자를 원래는 charAt을 통해 비교했는데, 이보다 startsWith를 사용하는게 추천되는 방식이라고 한다

 

사실 이 코드보다 더욱 간결하게 구현할 수도 있다고 한다

 

 

간결한 코드)

import java.util.*;
import java.util.stream.*;

class Solution {
	public String solution(int[] numbers) {
    	String answer = IntStream.of(numbers)
        	.mapToObj(String::valueOf)
            .sorted((s1, s2) -> (s2+s1).compareTo(s1+s2))
            .collect(Collectors.joining());
            
        if(answer.startsWith("0")) return "0";
        return answer;
    }
}

음.. 사실 이건 진짜 코테에서 내가 못쓸것 같아서 그냥 그렇구나.. 하고 넘어가려구!

 

그럼 빠잉!