Algorithm

하샤드의 수

1. 코딩테스트 연습 - 하샤드 수 | 프로그래머스 스쿨 (programmers.co.kr)
2. https://school.programmers.co.kr/learn/courses/30/lessons/12910

• 자릿수의 합 구하기 - step1
• 나누어 떨어지는 check 하기 - step2

자릿수의 합을 구하기

public class Hashad {
    public boolean solution(int x) {

        int sum = 0;
        int a = x;
        while (a > 0) {
            sum += a % 10; // 1의 자릿수부터 나눠가며 나머지 더하기
            a = a / 10; // sum에서 더해준 자릿수 빼기
        }

        if(x % sum == 0){
            return true;
        } else {
            return false;
        }
    }

}

a % 10 을 하면 1의 자리 수 부터 하나씩 더해주고 1의 자릿수 부터 더해주기 때문에

다음 숫자에서 변화해야 하기 때문에 나머지 10을 해서 1의 자릿수의 지워주고 그 수를 다시 돌려 그다음 자릿수를 더해준다.

나누어 떨어지는지 check 하기

public int[] solution2(int[] arr, int divisor) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % divisor == 0) {
                list.add(arr[i]);
            }
        }
				//list를 Array로 바꾸고
        if (list.size() == 0) return new int[]{-1};
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
				//sort한 것을 리턴
        Arrays.sort(answer);
        return answer;
    }

배열을 받아주고 그것을 divisor 로 나누었을때 0 인 수만 ArrayList에 넣어준다.

그 후 list.size가 0이라면 -1 을 넣고 리턴해주고 남은 결과는 다시 배열로 만들어 준 후 결과를 오름차 순으로 정리한 후 결과를 반환한다.

tip) Priority Queue사용해보기

일반적인 Queue란 일반적인 Queue는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First out)구조로 저장하는 선형 자료구조입니다. 하지만 Priority Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다.

PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다

데이터를 삽입할때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행한다.

우선순위 큐는 다음과 같은 속성을 가지고 있습니다.

1. 모든 항목에는 우선순위가 있습니다.
2. 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다.
3. 두 요소의 우선수위가 같은면 queue의 순서에 따라 제공됩니다.

4 → 9 → 2 순으로 데이터가 들어갔다고 했을 때 우선순위 큐의 처리 순서는 다음과 같다.

(높은 값의 높은 우선순위를 갖는다고 가정)

input: 4 → 9 → 2

일반적인 큐: 4 → 9 → 2

우선순위 큐: 9 → 4 → 2

Priority Queue 삽입 순서

Priority Queue 명령

priorityQueueLowest.poll() // 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.remove() // 첫번째 값을 제거 비어있다면 예외 발생 
priorityQueueLowest.peek() //첫번째 값을 반환만 하고 제거는 하지는 않는다. null반환
priorityQueueLowest.element() //첫번째 값을 반환만 하고 제거는 하지는 않는다. 예외 발생
priorityQueueLowest.clear() //초기화

우선순위 큐를 사용하여 나누어 떨어지는 수 구하기

public int[] solution3(int[] arr, int divisor){
        PriorityQueue<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()];
        int idx = 0;
        while(!list.isEmpty()){
            answer[idx++] = list.poll();
        }
        return answer;
    }

여기서 for문을 쓸 수 없는 이유는 queue에는 인덱스의 개념이 없기 때문이다. 그래서 while문으로 대체했다