구르는 돌에는 이끼가 끼지 않는다

타겟 넘버와 같은 경우 주어진 숫자에 +,- 두 연산을 통해서 원하는 숫자의 값이 나오는지 찾는 문제 이다. 

여기서 핵심은 역시나 +, - 조합을 통해서 원하는 계산 결과가 나오는 것인다. 

+, -의 조합은 결국 조합할 수 있는 모든 경우의 수를 접근 하는 것이다. 

여기서 핵심은 조합을 통한 경우의 수를 찾아야하는 경우 역시나 이전에 풀었던 소수 찾기와 마찬가지로 dfs를 이용하는 것이다. 

dfs는 트리 형태로 경우의 수를 찾아내는 방식이다. 

문제를 파악했을때 머리속에 트리 형태로 그림이 그려지도록 노력해야할 듯하다. 

package com.ji.study;

import static org.junit.Assert.assertEquals;

import org.junit.jupiter.api.Test;

public class TargetNumberTest {

	@Test
	void test() {

		TargetNumber test = new TargetNumber();
		
		assertEquals(5, test.solution(new int[] {1,1,1,1,1}, 3));
		assertEquals(3, test.solution(new int[] {2,3,5,7,9}, 2));
		assertEquals(1, test.solution(new int[] {1}, 1));
		assertEquals(5, test.solution(new int[] {6,2,3,6,7,1}, 7));

	}


}

package com.ji.study;

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

		solution(numbers, target);
		System.out.println("결과 : "+solution(numbers, target));
	}
	
	public static int solution(int[] numbers, int target) {
        int answer = 0;
        
        // DFS를 구성할때 numbers[0], -numbers[0]은 +식 -식을 넣는 경우의 간선을 의미함
        answer = dfs(numbers, target, numbers[0], 1) + dfs(numbers, target, -numbers[0], 1);
        
        return answer;
    }
    
    public static int dfs(int[] numbers, int target, int sum, int i) {
        
        if(i == numbers.length) {
            if(sum == target) {
                return 1;
            } else {
                return 0;
            }
        }
        
        int result = 0;
        //각 노드의 숫자들을 재귀적으로 더하거나 빼면서 계산함
        result += dfs(numbers, target, sum+numbers[i], i+1);
        result += dfs(numbers, target, sum-numbers[i], i+1);
        return result;
    }

}

[출처] lkhlkh23.tistory.com/74

programmers.co.kr/learn/courses/30/lessons/49993

스킬트리와 같은 경우는 java indexof() 메소드를 적극 활용하여서 풀었습니다.

하지만 스터디원같은 경우는 반복문을 많이 활용해서 풀어서 다양한 방법이 존재할 듯 합니다.

package com.ji.study;

import java.util.ArrayList;
import java.util.List;

public class Solution_49993 {

	public static void main(String[] args) {

//		테스트 케이스
//		"CBD" ["CAD"] 0
//		"CBD" ["AEF", "ZJW"] 2
//		"REA" ["REA", "POA"] 1
//		"CBDK" ["CB", "CXYB", "BD", "AECD", "ABC", "AEX", "CDB", "CBKD", "IJCB", "LMDK"] 4
//		"BDC" ["AAAABACA"] 0
//		"CBD" ["C", "D", "CB", "BDA"] 2

		String skill = "CBD";
		String[] skill_trees = { "AEF", "ZJW" };

		int result = solution(skill, skill_trees);
		System.out.println(result);
	}

	public static int solution(String skill, String[] skill_trees) {
		int skillTreeCnt = 0;

		for (String skillTree : skill_trees) {

			List<Integer> indexList = new ArrayList<Integer>();

			initSkillList(skill, skillTree, indexList);

			// skill_trees에 모두 없는 skill인 경우
			if (isWithoutSkill(indexList)) {
				skillTreeCnt++;
				continue;
			}

			// 첫번째 skill_trees안에 skill의 첫번째가 없는 경우 예외처리
			if (indexList.get(0) == 0)
				continue;

			// 하나의 스킬만 있는 skill_tress가 아니면서 마지막에 첫 스킬이 있는 경우 예외처리
			if (skillTree.length() != 1 && indexList.get(0) == skillTree.length())
				continue;

			initLastIndexZero(indexList);

			if (isAscendingOrder(indexList))
				skillTreeCnt++;

		}

		return skillTreeCnt;
	}

	// skill_tress index 검사 시 마지막에 -1인 경우에 대한 제거
	// 배열 안에 0 인 경우 제거
	public static void initLastIndexZero(List<Integer> indexList) {
		for (int i = indexList.size() - 1; i > 0; i--) {
			if (indexList.get(i) == 0) {
				indexList.remove(i);
			} else {
				break;
			}
		}
	}

	// 오름 차순으로 index를 가지고 있는 지 검사
	public static boolean isAscendingOrder(List<Integer> indexList) {
		boolean isOrderBy = true;
		for (int i = 0; i < indexList.size() - 1; i++) {
			if (indexList.get(i + 1) - indexList.get(i) < 0) {
				isOrderBy = false;
				break;
			}
		}
		return isOrderBy;
	}

	public static boolean isWithoutSkill(List<Integer> indexList) {
		boolean isAllZero = true;

		for (int i = 0; i < indexList.size(); i++) {
			if (!indexList.get(i).equals(0)) {
				isAllZero = false;
				break;
			}
		}

		return isAllZero;
	}

	public static void initSkillList(String skill, String skillTree, List<Integer> indexList) {
		// skill 문자열 초기화
		List<String> skilTreesList = new ArrayList<String>();
		for (char ski : skillTree.toCharArray()) {
			skilTreesList.add(String.valueOf(ski));
		}

		// skill_trees 문자열 초기화
		for (char ski : skill.toCharArray()) {
			int addIndex = skilTreesList.indexOf(String.valueOf(ski)) + 1;
			indexList.add(addIndex);
		}
	}

}

programmers.co.kr/learn/courses/30/lessons/42583

위 문제를 푸는데 가장 어려웠던 부분은 다리에 하중 예외처리와 이동 여부 처리의 부분이었다. 

다른 많은 예제를 통해서 간신히 풀게 되었다.

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

public class Solution_42583 {

// 테스트 케이스
//   solution(2, 10, new int[] {7,4,5,6}); //8
//   solution(3, 10, new int[] {7,4,5,6}); //11
//   solution(2, 10, new int[] {4,5,4,6}); //6
//   solution(2, 10, new int[] {7,4,5,4,6}); //8
//   solution(100, 100, new int[] {10}); //101
//   solution(100, 100, new int[] {10,10,10,10,10,10,10,10,10,10}); //110
//   solution(1, 2, new int[] {1,1,1}); //4
//   solution(1, 1, new int[] {1,1,1}); //4
//   solution(4, 2, new int[] {1,1,1,1}); //10
//   solution(3, 3, new int[] {1,1,1}); //6
//   solution(3, 1, new int[] {1,1,1}); //10
//   solution(3, 1, new int[] {1,1,1,1,1}); //16
//   solution(5, 5, new int[] {1,1,1,1,1,2,2}); //14
//   solution(7, 7, new int[] {1,1,1,1,1,3,3}); //18
//   solution(5, 5, new int[] {1,1,1,1,1,2,2,2,2}); //19
//   solution(5, 5, new int[] {2,2,2,2,1,1,1,1,1}); //19

	public static void main(String[] args) {

		int bridgeLength = 3;
		int weight = 10;
		int[] truckWeight = { 7,4,5,6 };
		int result = solution(bridgeLength, weight, truckWeight);

		System.out.println(result);

	}

	public static int solution(int bridge_length, int weight, int[] truck_weights) {

		Queue<TruckVO> passingTrucks = new LinkedList<TruckVO>();

		int shiftCount = 0, idx = 0, time = 0;

		while (idx < truck_weights.length) {

			if (!passingTrucks.isEmpty() && time == passingTrucks.peek().getMoveCnt()) {

				// 다리를 지남
				TruckVO vo = passingTrucks.poll(); 

				// 트럭이 나가서 하중 증가
				weight += vo.getWeight();
			}

			// 남은 하중 보다 트럭 하중이 작으면
			if (weight >= truck_weights[idx]) {
				// 배열 {진입한 트럭의 무게, 도달시간}
				TruckVO vo = new TruckVO();
				vo.setWeight(truck_weights[idx]);
				vo.setMoveCnt(time + bridge_length);
				passingTrucks.add(vo);
				// 트럭이 올라가고 남은 하중
				weight -= truck_weights[idx++];
			}

			time++;
		}
		
		shiftCount = time + bridge_length;
		return shiftCount;
	}

}

class TruckVO {
	int weight;
	int moveCnt;

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	public int getMoveCnt() {
		return moveCnt;
	}

	public void setMoveCnt(int moveCnt) {
		this.moveCnt = moveCnt;
	}
}