프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/12910

이전에 했던 하샤드 수를 판별하는 과정의 발전된 문제이다.

1. 문제

나누어 떨어지는 숫자 배열

• 배열을 통해 정수값들과 나누는 값이 제시가 되고 이를 통해 하샤드 수를 구해 리턴한다.

2. 문제분석

1. 배열을 통해 숫자 값들을 입력받음
2. 나누고 싶은 값을 설정함
3. 배열에 있는 값들을 나누고 싶은 값을 통해 나눔
4. 이때 나머지가 없이 딱 나누어지는 값을 배열에 넣어 리턴함
5. 만약 나머지가 없이 딱 나누어 떨어지는 값이 없을경우 -1 리턴
6. 리턴되는 결과값은 작은수부터 나올 수 있도록 정렬이 되어있어야함

---

🚫 제한조건 1. arr은 자연수를 담은 배열입니다. 2. 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다. 3. divisor는 자연수입니다. 4. array는 길이 1 이상인 배열입니다.

3. 설계

PriorityQueue( ) 사용

(1) PriorityQueue(우선순위 큐)란?

• Priority Queue는 Queue와 구조가 비슷하다. Queue는 FIFO구조로 먼저 들어온 값이 먼저 나가는 구조로 되지만 PriorityQueue는 거기에 발전해 FIFO를 기반으로 우선순위를 정해 우선순위가 높은 순서대로 나가게 된다.
• 우선순위 큐는 값을 비교해야하기 때문에 null값이 있으면 안된다.
• 내부구조는 이진트리 힙으로 구성되어 있어 add( ) 및 poll( ) 메서드 o(log(n))시간이 걸린다.

(2) PriorityQueue 선언

<// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());		
		
// String 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue3 = new PriorityQueue<>();

// String 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue4 = new PriorityQueue<>(Collections.reverseOrder());

① PriorityQueue 선언과 값 채우기

Queue<Integer> list = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
    if (arr[i] % divisor == 0) list.add(arr[i]);	// 배열의 값을 divisor로 나누어 0으로 딱 나누어 질때만 저장
}

② 하샤드 수가 없을경우 -1 리턴

if(list.size() == 0) return new int[]{-1};

③ List -> Array

int[] answer = new int[list.size()];        // 배열의 크기를 list크기만큼 설정 
int idx = 0;
while(!list.isEmpty()){                     // 리스트가 비어있지 않을경우
	answer[idx++] = list.poll();            // 배열에 리스트를 넣는다.
}

4. CODE

public class Harshad2 {
    // PriorityQueue() 사용해서 푸는 법
    // (Priority Queue는 기본큐의 기능인 FIFO를 가지면서 우선순위를 먼저 결정하고 우선순위가 높은 데이터가 먼저 나가는 자료구조이다)
    public int[] solution2(int[] arr, int divisor){
        Queue<Integer> list = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % divisor == 0) list.add(arr[i]);
        }

        if(list.size() == 0) return new int[]{-1};

        // list를 Array로 바꾸기
        int[] answer = new int[list.size()];        // 배열의 크기를 list크기만큼 설정 
        int idx = 0;
        while(!list.isEmpty()){                     // 리스트가 비어있지 않을경우
            answer[idx++] = list.poll();            // 배열에 리스트를 넣는다.
        }
        return answer;
    }

    public static void main(String[] args) {
        Harshad2 hs = new Harshad2();
        int[] arr ={5,9,7,10};
        int[] arr2 ={2,36,1,3};
        int[] arr3 = {3,2,6};
        System.out.println(Arrays.toString(hs.solution2(arr,5)));
        System.out.println(Arrays.toString(hs.solution2(arr2,1)));
        System.out.println(Arrays.toString(hs.solution2(arr3,10)));
    }
}