Python과 함께 춤을

1. 문제를 이해한다
입력값
- 정수배열 numbers와 목표 정수 target이 주어진다. 
결과값
- numbers의 값들을 더하거나 빼서 target값을 만들 수 있는 모든 경우의 수를 반환한다. 

2. 문제를 재정의한다.

3. 문제 풀이를 계획한다
- 배열을 순차적으로 깊이 우선 탐색을 시도한다. 
- 현재 탐색하고 있는 값을 더하거나 뺀 뒤 다음 배열값을 탐색한다. 

4. 문제 풀이를 검증한다.

5. 구현한다.

package dfs.bfs;

public class TargetNumber {

	public static void main(String[] args) {
 		int[] numbers = {1, 1, 1, 1, 1};
		int target = 3;
		solution(numbers, target);

	}
	
	public static int solution(int[] numbers, int target) {
        return processOne(numbers, 0, 0, target);
    }

	private static int processOne(int[] numbers, int n, int sum, int target) {
//		System.out.println("processOne " + n  + " "  + sum + " " + target);
		if(numbers.length == n) {
			if(sum == target) return 1;
			else return 0;
		}
		
		return processOne(numbers, n+1, sum+numbers[n], target) + processOne(numbers, n+1, sum-numbers[n], target); 
	}

}

6. 회고한다.
처음 시도할 때 매개변수로 count를 포함시켜 target을 찾았을 경우 count 변수에 1을 더한 뒤 count를 반환시키는 방향으로 구현을 했었다. 그러나 이러한 알고리즘은 첫 번째 processOne()에서 얻은 count가 두 번째 processOne()에 입력값으로 들어가게 되므로 두 번째 processOne()에서는 count가 0에서 시작하지 않는 경우가 발생.. 따라서 위와 같이 1 또는 0만을 반환시켜서 이를 모두 더하는 방향으로 수정하였음.

1. 문제를 이해한다
- 괄호와 사칙 연산을 이용하여 number를 n으로 표현한다. 그 중 n이 사용된 횟수가 가장 적은 경우의 횟수를 결과값으로 돌려준다.
- n : 1 ~ 9 사이의 정수 n이 주어진다. 
- number : 32000이하의 정수가 주어진다. 

2. 문제를 재정의한다.
- number(k) = (n이 k번 사용되어 나온 결과 값) = number(j) [+, -, *, /] number(k-j) (단,  j 는 1보다 크고 k보다 작다.  k-j는 0이 아니다.)

3. 문제 풀이를 계획한다
1) number(1)의 집합을 구한다 : {n} (주어진 n 1개로 이루어진 집합)
2) number(2)의 집합을 구한다 : {n} [+, -, *, /] {n}
...
n) number(k)의 집합을 구한다.
* number(k)의 집합은 Set으로 구현하여 중복을 제거한다.
* number(k)의 집합을 구하는 과정에서 주어진 number와 값이 같은 경우가 있을 경우 k값 반환 

4. 문제 풀이를 검증한다.
- 

5. 구현한다.

public static int solution(int N, int number) {
		/*
		 *  8개의 HashSet을 만든다. (0번째 HashSet은 사용하지 않음) 
		 */
		HashSet[] sets = new HashSet[9];
		for(int i=0; i<sets.length; i++) {
			sets[i] = new HashSet<Integer>();
		}
		/*
		 *  5, 55, 555, 5555 와 같은 값들은 연산의 결과 값이 아니므로
		 *  연산 이전에 미리 Set에 포함시킨다.
		 */
		for(int i=1; i<sets.length; i++) {
			String enumerate = "";
			for(int j=0; j<i; j++) {
				enumerate += N;
			}
			sets[i].add(new Integer(enumerate));
		}
		
		/*
		 * i 번째 set을 구한다.
		 * j번째 set과 (i-j)번째set을 사칙연산하여 결과 값을 i번째 set에 더한다. 
		 */
		for(int i=1; i<sets.length; i++) {
			for(int j=1; j<i; j++) {
				HashSet<Integer> preSet = sets[j];
				HashSet<Integer> postSet = sets[i-j];
				for(int k : preSet) {
					for(int l : postSet) {
						sets[i].add(k + l);
						sets[i].add(k * l);
						sets[i].add(Math.abs(k - l));
						if(l != 0) sets[i].add(k / l);
					}
				}
			}
			System.out.println(i + "set !!");
			System.out.println(sets[i]);
			if(sets[i].contains(number)) return i;
		}
		/*
		 * 8번째 set안에 포함되지 않았다는 것은 n이 9번 이상 필요하다는 것이므로
		 * -1을 반환한다. 
		 */
        int answer = -1;
        return answer;
    }

6. 회고한다.
 풀이 방법을 몰랐을 때는 엄한 방식으로 삽질하면서 "내가 풀 수 있는 수준인가" 싶었는데, 방법을 알고 한 단계 한 단계 풀어보니 생각보다 간단하다..