개발자를 향해...

프로그래머스 - 타켓 넘버 (java) 본문

코테 공부/프로그래머스master

프로그래머스 - 타켓 넘버 (java)

eugeneHwang1124 2022. 4. 5. 00:26
728x90
반응형

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

 

코딩테스트 연습 - 타겟 넘버

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수

programmers.co.kr

 

처음에 bfs인지 몰랐다. 그냥 첫번째 수부터 쭈르륵 + -를 모든 경우에 대해 연산하면 되는게 아닌가 했는데 문항 분류가 bfs로 되어있어서 신기했다. 내가 푼 방식은 BFS로 풀었고 코드는 다음과 같다.

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int[][] tree = new int [numbers.length][((int)Math.pow(2,numbers.length))]; 
        tree[0][0] = -numbers[0];
        tree[0][1] = numbers[0];
        // System.out.println(tree[0].length);
        
        for ( int i = 1; i < numbers.length; i++ ){
            int c = 0;
            for(int j=0; j<Math.pow(2,i); j++){
                int parent = tree[i-1][j];
                tree[i][c] = parent - numbers[i];
                c++;
                tree[i][c] = parent + numbers[i];
                c++;
            }
        }
        
//         for(int i = 0; i<tree.length; i++){
            
//             for(int j=0; j<tree[i].length; j++){
                
//                 System.out.print(tree[i][j]+" ");
//             }
//             System.out.println("");
//         }
        
        for(int i :tree[numbers.length-1]){
            if(i==target) answer++;
        }
        
        return answer;
    }
}

 

DFS의 코드는 아래 블로그를 참고하여 공부했다.

https://velog.io/@timointhebush/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-DFS-BFS-Python

 

프로그래머스 - 타겟 넘버 (DFS, BFS) Python

문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. `1+1+1+1+1

velog.io

DFS 함수를 선언하고 재귀 호출을 통해 깊이 내려간다. 여기서 내가 햇갈렸던 부분은 어떻게 + -를 구분하느냐인데

먼저 그냥 수 그러니깐 +에대해 재귀호출을 해준 후 각각에 대해 -를 차례대로 붙여서 다시 재귀호출을 해주면 + -를 모두 할 수 있는 방법이다.

 

느낀점

내가 dfs를 잘 이해하지 못한것 같다고 생각했다. dfs 유형을 더 연습해야겠다.

반응형