프로그래머스 Lv.2 : 타겟 넘버 🅾️

[문제]

n개의 음이 아닌 정수들이 있습니다.

이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때

숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

프로그래머스

 

[풀이]

class Solution {
    public static int[] mainNum; // 제공되는 숫자 배열
	public static int targetN; // 타겟 넘버
	public static int cnt=0; // 타겟 넘버를 만드는 방법의 수
	
	public static void cal(int index, int tmp, boolean type) {
		// index가 0보다 작거나 배열의 크기보다 크면 재귀 종료
		if(index<0 || index>mainNum.length) return;
		
		if(index==mainNum.length) {
			// 타겟 넘버와 일치하는지 확인
			if(tmp==targetN) cnt++;
			if(-tmp==targetN) cnt++;
			return;
		} else {
			if(type) tmp+=mainNum[index];
			else tmp-=mainNum[index];
			cal(index+1, tmp, true);
			// 계산 두 번 방지를 위해 if문 사용
			if(index!=mainNum.length-1) cal(index+1, tmp, false);
		}
    }
    
    public int solution(int[] numbers, int target) {
        mainNum=numbers;
		targetN=target;
		cal(0, 0, true);
        return cnt;
    }
}

 

연습보단 실전이라고 생각하며 풀어보기를 먼저 해보는 DFS 문제..!

재귀를 활용하여 DFS 알고리즘을 구현하는 기초적인 문제였던 것 같다.

나도 DFS를 모르는 상태에서 코딩테스트를 풀며 알고리즘을 배우듯 구현한 것이기 때문에,

DFS를 아는 사람이면 바로 로직이 눈에 보였을 것 같다. (나도 언젠가 그런 고수가 될 수 있겠지..)

시간은 20분에서 30분 정도 소요!

 

우선 내가 생각한 이 문제의 포인트는 '첫 번째 수'이다.

배열의 첫 번째 수부터 +와 -가 붙게 되는데..

사실 놀랍게도 🤤..! 첫 번째 수가 +가 붙는 경우 나오는 결과와, -가 붙는 경우 나오는 결과가 절댓값이 같다!!

그래서 나는 재귀를 덜 돌고 결과에 -가 붙는 경우 타겟 넘버와의 일치성까지 if로 한 번 검증해주었다.

 

물론 궁금해서 재귀를 다 돌고 if로 -가 붙는 경우를 제거도 해봤다. 결과는 아래와 같았다.

(1) 재귀를 반만큼 돌고 if를 한 번 더 붙인 경우

(2) 재귀를 다 돌고 if는 target과 같을 때 한 번만 체크하는 경우

차이가 보이는가...!! 난 잘 안 보인다..ㅜㅋㅋ

확실한건 테스트케이스에 따라 결과가 조금씩 다르다는 것인데,,

많은 양을 처리할때는 재귀를 차라리 다 돌아버리는 것이 빠르고, 적은 양을 처리할때는 내가 처음에 사용한 코드가 빠른 것 같다.

물론 현재 네트워크가 어떤가를 포함하여 운(?)도 있기 때문에 정확히 무슨 코드가 더 좋다고 하기엔 애매한 듯..

 

어쨌든 그런 포인트를 발견했다는 점도 나에게는 공부가 된 것 아닐까..라고 생각한다!^^

DFS 이론을 알기 보다는 먼저 코딩테스트를 풀어보는 것이 정답이었던 것 같다.

역시 사람은 연습보다는 실전파인것인가, 다음에는 BFS도 도전해보아야겠다. (자신감상승👍🏻)