프로그래머스 - 나누어 떨어지는 숫자 배열[java]

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12910

문제 설명:

입출력 예

arr

[5, 9, 7, 10][2, 36, 1, 3]
[3,2,6]

divisor

5
1
10

return

[5, 10][1, 2, 3, 36]
[-1]

파라미터로 들어온 arr의 값들이 divisor의 정수로 나뉘어 지면 결과값에 포함시켜서 오름차순으로 정렬시켜서 리턴하고 하나도 없으면 -1을 리턴하면 되는 문제이다.

문제 풀이

import java.util.*;
class Solution {
    public int[] solution(int[] arr, int divisor) {
        int[] answer = {-1};
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] % divisor == 0) {
                pq.add(arr[i]);
            }
        }
        if(pq.size() == 0) {
            return answer;
        } else {
            answer = new int[pq.size()];
            int i = 0;
            while(!pq.isEmpty()) {
                answer[i] = pq.poll();
                i++;
            }
        }
        return answer;
    }
}

문제 해설

arr를 스캔하여 나뉘어지는 값을 찾아서 정렬시키고 리턴하면 되는 문제이지만, 시간복잡도를 고려하여 우선순위큐를 사용하였다.

arr를 스캔하여 나뉘는 값을 찾아서 정렬할 경우의 시간 복잡도

arr 스캔: O(n)
추출한 리스트를 array로 변환: O(n)
리턴값 정렬: O(nlogn)

시간 복잡도 결과: 2(O(n)) + O(nlogn)

우선순위큐를 이용할 경우의 시간 복잡도

arr 스캔하면서 우선순위큐에 삽입: O(nlogn)
추출한 값 array에 삽입: O(nlogn)

시간 복잡도 결과: 2(O(nlogn))

퀵정렬의 평균이 nlogn인걸 감안했을때 차이가 없는듯 하다.....