[프로그래머스 - 자바(JAVA)] 33 : 타겟 넘버 | 최솟값 만들기

목차 📕

▸ 타겟 넘버
▸ 최솟값 만들기

---

✅ 타겟 넘버 : Lv.2

▼ 문제

출처 : 코딩테스트 연습 깊이/너비 우선 탐색(DFS/BFS) 타겟 넘버

▼ 내 풀이

• 피로도 문제 풀이을 참고했다.
• 깊이 우선 탐색(DFS)을 활용하여 문제에 접근했다.
• 0부터 시작해서 다음 노드를 -(numbers 내의 숫자), +(numbers 내의 숫자)로 하면 된다.
• 예를 들어 0을 시작 노드로 하고 numbers = [4, 1, 2, 1]일 때, 다음 노드는 -4, +4 이다.
• 이렇게 계산해 나가면서 깊이와 numbers 배열의 길이가 같을 때 계산을 멈춘다.

class Solution {
    public int count = 0;
    
    public int solution(int[] numbers, int target) {
        int answer = 0; 
        
        dfs(numbers, 0, target, 0);
        
        answer = count;
        
        return answer;
    }
    public void dfs(int[] numbers, int depth, int target, int result) {
        if(depth == numbers.length) {
            if(target == result) {
                count++;
            }
            return;
        }
        
        int plus = result + numbers[depth];
        int minus = result - numbers[depth];
        
        dfs(numbers, depth + 1, target, plus);
        dfs(numbers, depth + 1, target, minus);
    }
}

---

✅ 최솟값 만들기 : Lv.2

▼ 문제

출처 : 프로그래머스 코딩테스트 연습 > 연습문제 > 최솟값 만들기

▼ 내 풀이

• 두 배열을 정렬한다.
• A 배열은 오름차순으로 B 배열은 내림차순으로 정렬한다.
• 즉, A 배열의 작은 수는 B 배열의 큰 수와 곱하게 한다.

import java.util.*;

class Solution
{
    public int solution(int[] A, int[] B)
    {
        int answer = 0;
        
        //오름차순 정렬
        Arrays.sort(A);
        
        //내림차순 정렬
        Integer[] BInteger = Arrays.stream(B).boxed().toArray(Integer[]::new);
        Arrays.sort(BInteger, Collections.reverseOrder());

        for(int i = 0; i < A.length; i++) {
            answer += A[i]*BInteger[i];
        }
        return answer;
    }
}

• 코드 제출 결과, 정확성 테스트에서는 만점을 받았지만 효율성 테스트에서 한 테스트 케이스가 시간초과가 떴다.
• 찾아보니 Arrays.sort()가 효율성 테스트를 통과하지 못한다는 다른 사람들의 의견이 있었다.
• 해결방법으로 우선순위 큐를 활용하여 문제를 다시 풀어보았다.

import java.util.*;

class Solution
{
    public int solution(int[] A, int[] B) {
        int answer = 0;
        PriorityQueue<Integer> qA = new PriorityQueue<>();
        PriorityQueue<Integer> qB = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < A.length; i++) {
            qA.add(A[i]);
            qB.add(B[i]);
        }

        while (!qA.isEmpty()) {
            answer += qA.poll() * qB.poll();
        }

        return answer;
    }
}

▼ 알게된 점

우선순위 큐 PriorityQueue

• 우선순위 큐는 기본적으로 오름차순으로 요소를 정렬한다.
• 즉, 작은 값부터 큰 값 순서대로 요소가 정렬된다.
• 오름차순 정렬 : PriorityQueue<Integer> queue = new PriorityQueue<>();
• 내림차순 정렬 : PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
• Arrays.sort()로는 효율성 테스트를 통과하지 못했는데 우선순위 큐로 통과한 이유
  • Arrays.sort()는 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 배열을 정렬하는 데 필요한 추가적인 메모리가 필요하다.
  • 반면에 우선순위 큐는 삽입과 삭제 연산이 O(log n)의 시간 복잡도를 가지며, 힙(Heap) 자료구조를 사용하여 구현되어 메모리 사용량이 적다. 우선순위 큐는 정렬에 필요한 추가적인 메모리를 사용하지 않는다.

---