[프로그래머스] Lv2. 타겟 넘버 - Java

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

프로그래머스

---

풀이

방법1. DFS : Stack 이용

 

data(number 배열의 값)과 idx(number 배열의 인덱스)를 가진 Node 클래스를 이용하여 Stack으로 DFS 코드를 짰다.

import java.util.*;

class Solution {
    static class Node {
        int data;
        int idx;
        
        Node(int data, int idx) {
            this.data = data;
            this.idx = idx;
        }
    }
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        answer = DFS(numbers, target);
        
        return answer;
    }
    
    public static int DFS(int[] numbers, int target) {
        int answer = 0;
        Stack<Node> s = new Stack<>();
        s.push(new Node(numbers[0], 0));
        s.push(new Node(-numbers[0], 0));
        while(!s.isEmpty()) {
            Node curr = s.pop();
            if(curr.idx >= numbers.length-1) {
                if(curr.data == target) answer ++;
                continue;
            }
            
            int pos = curr.data+numbers[curr.idx+1];
            int neg = curr.data-numbers[curr.idx+1];
            s.push(new Node(pos, curr.idx+1));
            s.push(new Node(neg, curr.idx+1));
        }
        
        return answer;
    }
}

---

방법 2. DFS : 재귀함수 사용

 

위와 마찬가지로 data와 idx를 넘겨주는 재귀함수를 이용하여 DFS 코드를 짰다.

import java.util.*;

class Solution {
    static int answer;
    static int target;
    static int[] numbers;
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        Solution.numbers = numbers;
        Solution.target = target;
        
        DFS(numbers[0], 0);
        DFS(-numbers[0], 0);
        
        return answer;
    }
    
    public static void DFS(int data, int idx) {
        
        int pos = data+numbers[idx+1];
        int neg = data-numbers[idx+1];
        
        if(idx+1 >= numbers.length-1) {
            if(pos == target) answer++;
            if(neg == target) answer++;
            
            return;
        }
        
        DFS(pos, idx+1);
        DFS(neg, idx+1);
        
    }
}

---

회고

BFS 코드는 시간초과가 나서 쓰지 않았다.

 

처음 썼던 코드는 HashMap을 이용한 코드였는데, 제대로 된 탐색이 되지 않은 점이 문제였던 것 같다.

감을 잘 못잡아서 모든 경우를 어떻게 다 돌리지? 라는 생각을 많이 했는데 역시나 그래프 탐색이었다. DP문제로 푸는 건줄 알고 많이 고생했는데 프로그래머스에서  AI로 코드를 분석해주는 기능이 생겨서 그것을 통해 알아냈다. 괜찮은 기능인 것 같다. GPT를 돌려도 제대로 된 답변을 받기 어려운데 해당 문제를 학습한 AI를 제공받음으로써 더 나은 방법을 알 수 있다는 점이 좋았다. 게다가 한 문제에 10회나 AI를 사용할 수 있고, 학습을 통해 문제 추천해주는 기능이 정말 좋은 것 같다. 나같은 코테 초보자에게는 어떻게 해야하는지 막막한 경우가 많은데 이 점이 학습자들을 실력향상의 길로 이끌어줄 거라 생각한다. 하지만 몇몇 문제는 AI가 지원되지 않아 아쉽다. 더 많이 풀어서 데이터를 쌓아야 하는건가? ㅋㅋ 데이터를 쌓아드리기 위해 열심히 해야겠다.

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        int sum = 0;
        for(int i: numbers) {
            if(map.containsKey(i)) map.put(i, map.get(i)+1);
            else map.put(i, 1);
            sum += i;
        }
        if(sum == target) {
            answer = 1;
            return answer;
        }
        Arrays.sort(numbers);
        boolean[] visited = new boolean[numbers.length];
        
        for(int i=0; i<numbers.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                
                int idx = 0;
                while(sum != target) {
                    sum = 0;
                    
                    for(int j=0; j<numbers.length; j++) {
                        if(visited[j]) {
                            sum -= numbers[j];
                        } else {
                            sum += numbers[j];
                        }
                    }
                    
                    if(sum == target) {
                        int times = map.get(numbers[idx]);
                        answer += times;
                        
                        break;
                    }
                    
                    idx ++;
                    if(idx == numbers.length) break;
                }
                
            }
        }
        
        return answer;
    }
}