[프로그래머스] 타겟넘버 (Java)

[프로그래머스] 타겟넘버 (Java)

문제

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

풀이/후기

보통 DFS로 풀면 메모리랑, 효율로 더 좋게 풀 수 있는데

난 BFS가 익숙해서 그렇게 풀었당..

코드

import java.util.*;
import java.io.*;

class Solution {
    static Queue<Integer> q = new LinkedList<>();
    
    public int solution(int[] numbers, int target) {
        q.add(0); 
        
        for (int i = 0; i < numbers.length; i++) {
            int size = q.size();
            
            for (int j = 0; j < size; j++) {
                int current = q.poll(); 
                
                q.add(current + numbers[i]);
                q.add(current - numbers[i]);
            }
        }
        
        int result = 0;
        while (!q.isEmpty()) {
            if (q.poll() == target) {
                result++;
            }
        }
        
        return result;
    }
}

 

개선 전 코드

import java.util.*;
import java.io.*;

class Solution {
    static Queue<Integer> q = new LinkedList<>();
    
    public int solution(int[] numbers, int target) {
        
        q.add(numbers[0]);
        q.add(-numbers[0]);
        
        int result = 0;
        
        for (int i=1; i<numbers.length; i++){
            
            int size = q.size();
            while (size-- >0){
                int sum = q.poll();
                for (int j=0; j<2; j++){
                    int temp = 0;
                    if (j==0){
                        temp = sum + numbers[i];
                    } else {
                        temp = sum - numbers[i];
                    }
                    if (i == numbers.length - 1){
                        if(temp == target) result++;
                    } else {
                        q.add(temp);
                    }
                    
                }
                
            }
            
            
            
        }
        
        return result;
    }
    
}

 

Commit

https://github.com/KEA-MoGakCo/CodingTestStudy-Blue/commit/2cab15a17062f1876cdab4c4d92f620a510473df?diff=split&w=0

참고