[프로그래머스/java] 타겟 넘버 - BFS 이용

728x90

타겟 넘버

 

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 

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

 

이번 포스팅은 타겟 넘버입니다.

 

DFS나 BFS를 이용하여 푸는 문제입니다.

 

저는 BFS를 이용하여 풀었는데

 

처음에는 백트래킹(완전탐색)을 이용하여 테스트케이스를 풀었으나,

제출 시 시간초과가 4개의 케이스에서 발생했습니다.

 

반응형

 

BFS를 이용해서 풀면 시간초과가 나지 않고 풀 수 있습니다.

 

Solution 클래스에 선언할 변수들은

• int cnt = 0;
• int[] numArr;
• int[] op = {1, -1};
• class Num 
  • int val;
  • int cnt;

 

cnt는 정답이 되는 방법의 갯수입니다. 

numbers의 길이만큼 순회했을 때 계산 값이 target이랑 같은지 체크한 후, cnt를 증가시킵니다.

 

numArr 배열은 numbers를 clone하여 복제한 후, 순회할 때마다 해당 순번의 숫자를 구하는 용도입니다.

 

op는 numArr 배열에서 해당 순번의 숫자를 구한 후, 합계에 숫자를 곱하여 연산할 수를 구할 용도로 사용합니다.

 

풀이 과정

1. Num 클래스를 넣을 수 있는 Queue를 생성합니다.
2. Queue에서 Num을 뽑으며 순회할 때마다 해당 순번의 숫자에 1, -1을 곱하여 연산수를 만듭니다.
3. 연산수를 합계에 더하여 다음 순회를 합니다.
4. 순회의 횟수가 numbers의 길이만큼 돌았는지 검사합니다.
5. 검사 후 target과 합산 값이 같으면 cnt를 증가시킵니다.
6. Queue가 비워질 때까지 반복합니다.

package dfsAndBfs;

/**
 * https://programmers.co.kr/learn/courses/30/lessons/43165?language=java
 * 
 * 타겟넘버
 * 
 * 백트래킹을 이용하여 풀려하였으나 시간초과 발생
 * 
 * BFS를 이용하면 손쉽게 풀 수 있음
 */

import java.util.LinkedList;
import java.util.Queue;

public class TargetNumber {
	public static void main(String[] args) {
		Solution s = new Solution();
		int[] numbers = {1,1,1,1,1};
		int target = 3;
		System.out.println(s.solution(numbers, target));
	}
}

class Solution {
	int cnt = 0;
	int[] numArr, op = {1, -1};
	class Num {
		int val, cnt;
		public Num(int val, int cnt) {
			this.cnt = cnt;
			this.val = val;
		}
	}
	
    public int solution(int[] numbers, int target) {
        check = new boolean[numbers.length];
        numArr = numbers.clone();
        bfs(numbers.length, target);
        return cnt;
    }
    
    public void bfs(int n, int target) {
    	Queue<Num> q = new LinkedList<Num>();
    	q.add(new Num(0, 0));
    	
    	while(!q.isEmpty()) {
    		Num num = q.poll();
    		
    		if(num.cnt == n) {
    			if(num.val == target) cnt++;
    			continue;
    		}
    		
    		for (int i = 0; i < 2; i++) {
				int val = num.val + numArr[num.cnt]*op[i];
				q.add(new Num(val, num.cnt + 1));
			}
    	}
    }
}