[1일 1알고리즘] 프로그래머스 - 타겟 넘버

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

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

어제 새벽늦게자서 컨디션이 별로지만 하기싫어도 꾸준히 해야 습관이 들겠지... 흨

하지만 컨디션 때문인지는 몰라도 푸는데 생각보다 시간이 걸렸다.

수도코드

function dfs(level, sum){
	if(level이 배열numbers의 길이와 같다면) {
    	if(sum 이 target값과 같다면)
        	answer <- answer + 1
        return
    }
    
    dfs(level+1, sum + 배열 p_integer의 level인덱스의 값)
    dfs(level+1, sum - 배열 p_integer의 level인덱스의 값)
}

최악의 케이스가 2^20(1MB) 으로 알고리즘 최악시간복잡도가 크지않기 때문에 dfs 이용가능.

+와 -를 구별하여 깊이우선탐색 진행하고 마지막 깊이에 도달할 경우 가지치기를 통해 정답케이스를 전역변수에 저장.

 

제출정답코드(가급적 정답을 맞추기전에 보지말고 스스로 푸세요)

class Solution {
    static int answer, goal;
    static int[] p_integer;
    public int solution(int[] numbers, int target) {
        p_integer = new int[numbers.length];
        for(int i = 0; i<numbers.length; i++)
            p_integer[i] = numbers[i];
        goal = target;
        answer = 0;
        dfs(0, 0);
        return answer;
    }
    
    private static void dfs(int level, int sum){
        if(level == p_integer.length){
            if(sum == goal)
                answer++;
            return;
        }
        
        dfs(level+1, sum + p_integer[level]);
        dfs(level+1, sum - p_integer[level]);
    }
}

- 배열복사시 for-each문을 생각없이 쓰다가 정답이 안나와서 당황.

=> for-each의 경우 인덱스를 활용해야할때는 부적합하다.

- for문 말고 Arrays.copyOf(원본배열,원본배열에서 복사하고 싶은만큼의 길이)를 사용해도됨.