[프로그래머스] Lv 2 가장 큰 수 Java 풀이

1. 문제에 대하여 📦

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746

(1) 조건 분석 📊

배열에 주어진 숫자들을 일렬로 나열해서 최대값을 만들어야 한다.
[6, 10, 2] -> 6210

2. 코드가 나오기까지 🛠️

KEY WORD: 정렬, Comparator

배열 진행은 다음과 같이 한다. a, b 가 있다고 했을 때,

• ab, ba 구조의 숫자를 만든다 .
• 이 둘의 대소관계를 비교해서 내림차순으로 정리한다.

이를 위해서 Arrays.sort() 를 사용했고, int를 Integer Wrapper Class로 교환했다.
이렇게 한 이유는 Arrays.sort()에 두번째 인자인 Comparator를 오버라이딩할 경우, 첫 번째 인자가 객체 배열이여야 하기 때문이다. 하지만, 처음에 주어진, numbers의 경우 int 배열이라, 이러한 재정의 방식을 쓸 수가 없다.

(1) 시간복잡도 분석 ⏳

sorting 작업은 O(nlogn)이다. 여기서 n이 되는 배열의 길이가 최대 100,000개 이므로, 충분히 가능하다.

3. 코드 🌐

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        Integer [] nums = new Integer [numbers.length];
        for(int i = 0; i < nums.length; i++){
            nums[i] = numbers[i];
        }

        Arrays.sort(nums,             
            (a,b) -> {
                StringBuilder candi1 = new StringBuilder();
                StringBuilder candi2 = new StringBuilder();
                candi1.append(a).append(b);
                candi2.append(b).append(a);
                return Integer.parseInt(candi2.toString()) - Integer.parseInt(candi1.toString());
            });

        StringBuilder answer = new StringBuilder();
        for(int temp : nums){
            answer.append(temp);
        }
        if(answer.charAt(0) == '0') {
            answer.setLength(0);
            answer.append(0);
        }
        return answer.toString();
    }
}

4. 트러블 슈팅 or 배운 점📝

(1) Arrays.sort() 에서 Comparator를 Overriding 할 시 주의점

Arrays.sort()에서 Comparator를 Overriding하여 사용하려면, 첫 번째 인자가 객체 배열이어야 한다.

(2) PriorityQueue의 내부는 전체 정렬 상태가 아니다.

PriorityQueue는 배열을 이용해, 최소힙, 최대힙 이진 트리를 구현한 자료구조이기 때문에, peek()의 값이, 정렬 순서의 첫 번째 값인 것은 보장하지만, 그 이후의 값들이 순차적으로 정렬되어 있지는 않다. (형제 노드끼지는 뭐가 큰 지 모르는 것처럼)

이것을 모르고 풀었다가 틀렸었다.