[자바(JAVA)] 정수 내림차순으로 배치하기. PriorityQueue<Long>

 

https://school.programmers.co.kr/learn/courses/30/lessons/12933

 

프로그래머스

 

 

---

✅ 내 풀이

public long solution(long n) {
            ArrayList<Integer> temp = new ArrayList<>();
            while(n > 0){
                temp.add((int)(n % 10));
                n /= 10;
            }

            Collections.sort(temp, Collections.reverseOrder());

            StringBuilder result = new StringBuilder();
            for (int digit : temp) {
                result.append(digit);
            }

            return Long.parseLong(result.toString());
        }

 

나는 long 타입의 매개변수를 각 자리별로 하나씩 끊어서 저장을 했다.

기존에 들어온 n값과 순서가 달라지지만 이 문제에서 어차피 정렬을 요구했기 때문에 순서에 상관없이 temp에 저장했다.

 

이후 sort의 조건을 주어 내림차순으로 변경했고 Long타입으로 변환하기 위해 StringBuilder에 담아서 처리했다.

 

문제를 제출한 후 내 눈에 띄는 다른 정답이 있었다.

 

 

✅ 다른풀이 1

public long solution(long n) {
        long answer = 0;
        String[] str = Long.toString(n).split("");
        PriorityQueue<Long> arr = new PriorityQueue<>(Collections.reverseOrder());
        for (String s:str)
            arr.add(Long.parseLong(s));
        while(!arr.isEmpty()){
            answer=answer*10+arr.poll(); // poll() -> 값을 제거 peek() -> 값을 제거하지 않음
        }

        return answer;
    }

👉 PriorityQueue의 poll() 메서드는 우선순위 큐에서 가장 작은(또는 가장 큰, 우선순위에 따라 다름) 요소를 꺼내오는 것이다.

이후 poll()을 한다면 정렬된 상태에서 우선순위에 따라 가장 작은 요소가 반환된다.

PriorityQueue를 사용한 코드에서는 poll() 메서드를 사용하는 과정에서 올바른 순서로 요소를 꺼내온다.

정렬된 상태에서는 가장 큰 숫자가 우선순위 큐에서 가장 작은 요소로 취급되어 반환하기 때문에 PriorityQueue를 사용하는 것이 더 나은 선택이라고 볼 수 있다.

 

사용된 PriorityQueue는 힙(heap) 자료구조를 기반으로 하며, 이는 우선순위 큐에 특화되어 있다.

힙은 원소를 삽입하거나 삭제할 때 O(log N)의 시간 복잡도를 가지며, 항상 가장 우선순위가 높은 원소가 루트에 위치하므로 가장 큰 원소를 꺼내는 것이 빠르게 이루어집니다.

 

 

💬 내 코드와 비교했을때는 어떨까?

📌 ArrayList를 사용하는 경우, 원소를 추가하고 정렬하는 데에 O(N log N)의 시간이 소요됩니다.
따라서 PriorityQueue를 사용하는 것이 일반적으로 더 효율적입니다. 

PriorityQueue는 우선순위 큐로서, 숫자를 추가하면 내부적으로 가장 큰 값이 먼저 나오도록 관리됩니다. 따라서 입력 숫자의 각 자릿수를 PriorityQueue에 추가하면, 우선순위 큐의 특성에 따라 가장 큰 숫자부터 차례대로 꺼내서 사용할 수 있습니다. 이렇게 하면 PriorityQueue를 사용하여 더 간결하고 효율적인 코드를 작성할 수 있습니다.