[Programmers 문제풀이 JAVA] Level 2 가장 큰 수

 

📄 가장 큰 수

🔗 문제 풀러가기

---

문제는 문자열의 정렬을 이용하여 해결하였습니다. 가장 큰 수를 만드는 방법은 가장 큰 수가 앞으로 오면 됩니다. 여기서 가장 큰 수는 0 ~ 9 중 가장 큰 수를 말합니다. 즉, 30 보다는 9가 앞으로 와야지 더 큰 수가 되는 것입니다.

처음 문제를 접근 할 때에는 그냥 문자열 정렬을 한 뒤 모든 수를 이어 붙이면 가능할거라 생각했지만 함정이 존재 했습니다. 아래는 문제의 예제중 하나 입니다.

예제 1

(3, 30, 34, 5, 9)

여기서 단순 문자열 정렬을 한다면 아래와 같은 순서로 정렬이 됩니다.

(9, 5, 34, 30, 3)

이대로 이어 붙인다면 9534303이라는 결괏값이 나오게 되는데 문제의 정답은 9534330입니다. 즉 단순 정렬이 아니라 정렬의 조건을 줘야 한다는 뜻입니다. 그렇다면 어떻게 정렬 할 것인지에 대한 조건을 생각해보면 다음과 같이 생각할 수 있습니다.

정렬 조건

두 수 3, 31이 있을 때 331 과 313의 크기를 비교해 정렬합니다. 즉 두 수를 이어 붙였을 때 더 큰수가 될 수 있는 순서대로 정렬을 진행하면 됩니다.

예외 처리

위와 같은 방법으로 문제를 해결할 수 있지만 한 가지 테스트케이스 에서 실패를 반환하게 됩니다. 문제의 조건 중 원소는 0이상이라는 조건을 처리해주지 않아서 입니다. 만약 (0,0,0,0)의 배열이 주어 졌을 때 0000이 아닌 0을 출력해줘야 합니다. 따라서 가장 큰 수를 기준으로 정렬되어 있는 배열에서 첫 번째 원소가 0이라면 그냥 "0"을 출력해주도록 예외 처리를 해줘야 합니다.

글보단 소스코드를 보면 쉽게 이해할 수 있습니다.

 

---

🌱 Solution 함수

주어진 int[]를 String[]로 변환된 값을 받고 문자열 정렬을 진행합니다.

public String solution(int[] numbers) {
        String[] nums = toStringArray(numbers);
        Arrays.sort(nums, (s1, s2) -> (s2 + s1).compareTo(s1 + s2));
        return makeMaxNum(nums);
    }

🌱 makeMaxNum 함수

큰 수를 만들 수 있도록 정렬된 배열을 합치는 함수입니다.

private String makeMaxNum(String[] nums) {
        if (nums[0].equals("0")) return "0";
        StringBuilder result = new StringBuilder();
        for (String item : nums)
            result.append(item);

        return result.toString();
    }

🌱 toStringArray 함수

int형 배열을 String형 배열로 변환하는 함수 입니다.

private String[] toStringArray(int[] arr) {
        String[] ret = new String[arr.length];
        for (int i = 0; i < arr.length; i++)
            ret[i] = String.valueOf(arr[i]);
        return ret;
    }

---

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이