개발 학습 블로그

public class Solution {
	
	// 순위
	// Floyd Warshall 알고리즘으로 풀이
	
	public static int solution(int n, int[][] results) {
		int answer = 0;
		int zeroCnt = 0;
		int[][] board = new int[n][n]; // 0 ~ 4
		
		for (int i = 0; i < results.length; i++) {
			// {4, 3}의 경우
			board[results[i][0] - 1][results[i][1] - 1] = 1; // 4는 3에게 이겼으므로 board[3][2] = 1
			board[results[i][1] - 1][results[i][0] - 1] = -1; // 3은 4에게 졌으므로 board[2][3] = -1
		}
		
//		0 : {0, 1, 0, 0, 0}
//		1 : {-1, 0, -1, -1, 1}
//		2 : {0, 1, 0, -1, 0}
//		3 : {0, 1, 1, 0, 0}
//		4 : {0, -1, 0, 0, 0}
		
		for (int k = 0; k < n; k++) {
			
			for (int i = 0; i < n; i++) {
				
				for (int j = 0; j < n; j++) {
					
					if (k == i || i == j || k == j) { // 자기 자신과의 경기는 있을 수 없다.
						continue;
					}
					
					if (board[i][j] == 0) { // i와 j의 경기 결과를 분실했다면
						
						if (board[i][k] == 1 && board[k][j] == 1) { // i가 k에게 이기고, k가 j에게 이겼다면
							board[i][j] = 1; // i는 j에게 이긴 것으로 체크
						} else if (board[i][k] == -1 && board[k][j] == -1) { // i가 k에게 지고, k가 j에게 졌다면
							board[i][j] = -1; // i는 j에게 진 것으로 체크
						}
					}
				}
			}
		}
		
//		0 : {0, 1, 0, 0, 1}
//		1 : {-1, 0, -1, -1, 1} // 자기 자신을 제외하고 다른 모든 선수들과의 경기 결과를 알 수 있는 선수
//		2 : {0, 1, 0, -1, 1}
//		3 : {0, 1, 1, 0, 1}
//		4 : {-1, -1, -1, -1, 0} // 자기 자신을 제외하고 다른 모든 선수들과의 경기 결과를 알 수 있는 선수
		
		for (int i = 0; i < n; i++) {
			
			zeroCnt = 0;
			
			for (int j = 0; j < n; j++) {
				
				if (board[i][j] == 0) {
					zeroCnt++;
				}
			}
			
			if (zeroCnt == 1) {
				answer++;
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 5;
		int[][] results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};
		
		System.out.println(solution(n, results)); // 2
	}
}

import java.util.HashMap;

public class Solution {
	
	// 롤케이크 자르기
	
	public static int solution(int[] topping) {
		int answer = 0;
		
		HashMap<Integer, Integer> hm1 = new HashMap<>();
		HashMap<Integer, Integer> hm2 = new HashMap<>();
		
		for (int i = 0; i < topping.length; i++) {
			hm2.put(topping[i], hm2.getOrDefault(topping[i], 0) + 1);
		}
		
		// hm2 : {1=4, 2=2, 3=1, 4=1}
		
		for (int i = 0; i < topping.length; i++) {
			hm1.put(topping[i], hm1.getOrDefault(topping[i], 0) + 1);
			
			if (hm2.containsKey(topping[i])) {
				hm2.put(topping[i], hm2.get(topping[i]) - 1);
			}
			
			if (hm2.get(topping[i]) == 0) {
				hm2.remove(topping[i]);
			}
			
			if (hm1.size() == hm2.size()) { // hm1 : {1=2, 2=1, 3=1}, hm2 : {1=2, 2=1, 4=1} // hm1 : {1=3, 2=1, 3=1}, hm2 : {1=1, 2=1, 4=1}
				answer++;
			}
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] topping = {1, 2, 1, 3, 1, 4, 1, 2}; // 1, 2, 1, 3과 1, 4, 1, 2로 잘랐을 떄, 1, 2, 1, 3, 1과 4, 1, 2로 잘랐을 때
		
		System.out.println(solution(topping)); // 2
	}
}

<객체 비교>

== : 동일성 비교(객체 인스턴스의 주소 값을 비교)

equals() : 동등성 비교(객체 내부의 값을 비교)

hashCode() : 객체의 메모리 번지를 이용해서 해시코드를 만들고 그 값을 리턴(객체마다 다른 값을 가지고 있다.)

hashCode()를 사용하는 이유 중 하나는, 객체를 비교할 때 드는 비용을 낮추기 위함이다.

자바에서 2개의 객체가 같은지 비교할 때 equals()를 사용하는데, 여러 객체를 비교할 때 equals()를 사용하면 Integer를 비교하는 것에 비해 많은 시간이 소요된다.

hashCode() 메소드를 실행하여 리턴된 해시코드 값이 다르면 다른 객체로 판단하고, 해시코드 값이 같으면 equals() 메소드로 두 객체를 다시 비교한다.

즉, 여러 객체의 동등성 비교를 할 때
hashCode() 메소드를 실행해 값이 같을 경우에만 equals() 메소드로 동등성을 비교하면 되는 것이다.
hashCode() 값이 다르면 애초에 비교할 필요가 없게 된다.

hashCode가 다르면, 두개의 객체가 같지 않다.

hashCode가 같으면, 두개의 객체가 같거나 다를 수 있다.

<equals()와 hashCode()를 같이 재정의해야 하는 이유>

1. hashCode()를 재정의 하지 않으면 같은 값 객체라도 해시값이 다를 수 있다. 따라서 HashTable에서 해당 객체가 저장된 버킷을 찾을 수 없다.

2. equals()를 재정의하지 않으면 hashCode()가 만든 해시값을 이용해 객체가 저장된 버킷을 찾을 수는 있지만 해당 객체가 자신과 같은 객체인지 값을 비교할 수 없기 때문에 null을 리턴하게 된다.

<equals()만 재정의>

public class Test {
	String name;
	
	public Test(String name) {
		this.name = name;
	}

	@Override
	public boolean equals(Object obj) {
		Test otherTest = (Test) obj;
		return (this.name.equals(otherTest.name));
	}
}

import java.util.HashMap;

public class EqualsAndHashCode {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1 = "Z@S.ME";
		String str2 = "Z@RN.E";
		
		HashMap<String, Integer> hm1 = new HashMap<>();
		
		hm1.put(str1, 30);
		hm1.put(str2, 40);
		System.out.println(str1.equals(str2)); // false
		System.out.println(str1.hashCode()); // -1656719047
		System.out.println(str2.hashCode()); // -1656719047
		System.out.println(hm1.size()); // 2
		System.out.println(hm1.get(str1)); // 30
		System.out.println(hm1.get(str2)); // 40
		
		Test test1 = new Test("abcd");
		Test test2 = new Test(new String("abcd"));
		
		HashMap<Test, Integer> hm2 = new HashMap<>();
		
		hm2.put(test1, 10);
		hm2.put(test2, 20);
		System.out.println(test1.equals(test2)); // true
		System.out.println(test1.hashCode()); // 474675244
		System.out.println(test2.hashCode()); // 932583850
		System.out.println(hm2.size()); // 2
		System.out.println(hm2.get(test1)); // 10
		System.out.println(hm2.get(test2)); // 20
	}
}

<hashCode()만 재정의>

public class Test {
	String name;
	
	public Test(String name) {
		this.name = name;
	}
	
	@Override
	public int hashCode() {
		int hashCode = 0;
		hashCode = 31 * hashCode + ((name == null) ? 0 : name.hashCode());
		return hashCode;
	}
}

import java.util.HashMap;

public class EqualsAndHashCode {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1 = "Z@S.ME";
		String str2 = "Z@RN.E";
		
		HashMap<String, Integer> hm1 = new HashMap<>();
		
		hm1.put(str1, 30);
		hm1.put(str2, 40);
		System.out.println(str1.equals(str2)); // false
		System.out.println(str1.hashCode()); // -1656719047
		System.out.println(str2.hashCode()); // -1656719047
		System.out.println(hm1.size()); // 2
		System.out.println(hm1.get(str1)); // 30
		System.out.println(hm1.get(str2)); // 40
		
		Test test1 = new Test("abcd");
		Test test2 = new Test(new String("abcd"));
		
		HashMap<Test, Integer> hm2 = new HashMap<>();
		
		hm2.put(test1, 10);
		hm2.put(test2, 20);
		System.out.println(test1.equals(test2)); // false
		System.out.println(test1.hashCode()); // 2987074
		System.out.println(test2.hashCode()); // 2987074
		System.out.println(hm2.size()); // 2
		System.out.println(hm2.get(test1)); // 10
		System.out.println(hm2.get(test2)); // 20
	}
}

<equals()와 hashCode() 모두 재정의>

public class Test {
	String name;
	
	public Test(String name) {
		this.name = name;
	}

	@Override
	public boolean equals(Object obj) {
		Test otherTest = (Test) obj;
		return (this.name.equals(otherTest.name));
	}
	
	@Override
	public int hashCode() {
		int hashCode = 0;
		hashCode = 31 * hashCode + ((name == null) ? 0 : name.hashCode());
		return hashCode;
	}
}

import java.util.HashMap;

public class EqualsAndHashCode {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1 = "Z@S.ME";
		String str2 = "Z@RN.E";
		
		HashMap<String, Integer> hm1 = new HashMap<>();
		
		hm1.put(str1, 30);
		hm1.put(str2, 40);
		System.out.println(str1.equals(str2)); // false
		System.out.println(str1.hashCode()); // -1656719047
		System.out.println(str2.hashCode()); // -1656719047
		System.out.println(hm1.size()); // 2
		System.out.println(hm1.get(str1)); // 30
		System.out.println(hm1.get(str2)); // 40
		
		Test test1 = new Test("abcd");
		Test test2 = new Test(new String("abcd"));
		
		HashMap<Test, Integer> hm2 = new HashMap<>();
		
		hm2.put(test1, 10);
		hm2.put(test2, 20);
		System.out.println(test1.equals(test2)); // true
		System.out.println(test1.hashCode()); // 2987074
		System.out.println(test2.hashCode()); // 2987074
		System.out.println(hm2.size()); // 1
		System.out.println(hm2.get(test1)); // 20
		System.out.println(hm2.get(test2)); // 20
	}
}

equals()만 재정의 : equals()가 true이고, hashCode()가 다른 경우 => HashMap에서 다른 key로 인식

hashCode()만 재정의 : equals()가 false이고, hashCode()가 같은 경우 => HashMap에서 다른 key로 인식

equals()와 hashCode() 모두 재정의 : equals()가 true이고, hashCode()가 같은 경우 => HashMap에서 같은 key로 처리

첫 시도에서 런타임 에러가 발생해 다른 방법으로 풀이하였다.

import java.util.HashSet;

public class Solution {
	
	// 등대
	
	public static int solution(int n, int[][] lighthouse) {
		int answer = 0;
		int[] linkedCntArr; // 각 등대에 연결된 등대의 수를 입력받기 위한 배열
		
		HashSet<Integer> edgeHs = new HashSet<>(); // 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대의 번호를 담을 HashSet
		HashSet<Integer> turnOnHs = new HashSet<>(); // 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된, 반드시 켜야 하는 등대의 번호를 담을 HashSet
		int[][] remainingLightHouse; // 반드시 켜야 하는 등대를 킨 후 남은 등대 쌍을 담을 2차원 배열
		int remainingCnt; // remainingLightHouse에 담긴 등대 쌍의 수
		
		// CASE 1을 기준으로 설명
		
		for (int a = 0; a < n; a++) { // 과정 반복
			
			// 현재 turnOnHs가 비어있지 않은 상황이라면, turnOnHs에 담긴 번호의 등대를 킨 상황으로, 켜진 등대의 영향을 받는 등대는 고려해야 할 대상에서 제외한다.(lighthouse의 길이가 줄었을 것)
			
			linkedCntArr = new int[n + 1]; // linkedCntArr 초기화 // 0 ~ n
			remainingLightHouse = new int[lighthouse.length][2]; // remainingLightHouse 초기화
			remainingCnt = 0; // remainingCnt 초기화
			
			for (int i = 0; i < lighthouse.length; i++) {
				linkedCntArr[lighthouse[i][0]]++;
				linkedCntArr[lighthouse[i][1]]++;
			}
			
			// linkedCntArr : {0, 4, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 3, 1, 1}
			
			for (int i = 0; i < linkedCntArr.length; i++) {
				
				if (linkedCntArr[i] == 1) { // 연결된 등대가 하나뿐이라면 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대
					edgeHs.add(i); // edgeHs에 등대 번호 담기
				}
			}
			
			// edgeHs : [3, 4, 7, 8, 11, 13, 14]
			
			for (int i = 0; i < lighthouse.length; i++) {
				
				// 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된 등대 번호를 turnOnHs에 담기 // 반드시 켜야 하는 등대 번호
				
				if (edgeHs.contains(lighthouse[i][0]) || edgeHs.contains(lighthouse[i][1])) {
					
					if (edgeHs.contains(lighthouse[i][0])) {
						turnOnHs.add(lighthouse[i][1]);
					} else {
						turnOnHs.add(lighthouse[i][0]);
					}
				}
			}
			
			// turnOnHs : [1, 6, 10, 12]
			
			for (int i = 0; i < lighthouse.length; i++) {
				
				// turnOnHs에 담긴 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍이 있는지 확인
				
				if (!turnOnHs.contains(lighthouse[i][0]) && !turnOnHs.contains(lighthouse[i][1])) {
					remainingLightHouse[remainingCnt] = lighthouse[i];
					remainingCnt++;
				}
			}
			
			// remainingLightHouse : {{2, 9}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}
			// remainingCnt == 1
			
			if (remainingCnt == 0) { // 현재 켜진 등대로 모든 등대를 밝힐 수 있다면
				break;
			}
			
			if (remainingCnt == 1) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍이 1쌍 존재한다면
				answer += 1; // 남은 1쌍의 등대 중 어떤 등대를 켜도 되기 때문에 1만 증가
				break;
			}
			
			if (remainingCnt < lighthouse.length) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍의 수가 2 이상 lighthouse.length 미만이라면
				lighthouse = new int[remainingCnt][2]; // lighthouse의 길이 줄이기
				
				for (int i = 0; i < remainingCnt; i++) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍만 고려하면 된다.
					lighthouse[i] = remainingLightHouse[i];
				}
			}
			
			// 다시 for문으로 가 과정 반복
		}
		
		answer += turnOnHs.size(); // 켜진 등대의 수를 더해준다.
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// CASE 1
		int n = 14;
		int[][] lighthouse = {{4, 1}, {5, 1}, {5, 6}, {7, 6}, {1, 2}, {1, 3}, {6, 8}, {2, 9}, {9, 10}, {10, 11}, {5, 12}, {12, 13}, {12, 14}};
		// CASE 2
//		int n = 10;
//		int[][] lighthouse = {{4, 1}, {5, 1}, {5, 6}, {7, 6}, {1, 2}, {1, 3}, {6, 8}, {2, 9}, {9, 10}};
		// CASE 3
//		int n = 8;
//		int[][] lighthouse = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {5, 6}, {5, 7}, {5, 8}};
		
		System.out.println(solution(n, lighthouse));
	}
}

2022.11.17 기준 정답률이 6%밖에 안되는 문제이기 때문일까? 점수를 13점이나 준다.

내가 풀이한 방법은 이렇다.

STEP 1. 반드시 켜야 하는 등대의 기준

가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된 등대는 반드시 켜야 한다.

가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대는 lighthouse 배열의 원소들 중 하나만 존재하는 번호에 해당하며,

그 번호와 쌍을 이루는 번호는 반드시 켜야 하는 등대의 번호를 의미한다.

STEP 2. 반드시 켜야 하는 등대의 번호를 HashSet에 담고, lighthouse 배열의 원소들 중 HashSet에 존재하는 번호가

있을 경우, 그 번호를 포함한 등대 쌍(배열)을 제거한다. => 현재 켜진 등대로 밝힐 수 없는 등대 쌍만 남게 된다.

STEP 3. STEP 2에서 남은 등대 쌍으로 lighthouse 배열을 다시 만든다.

STEP 4. STEP 1부터 과정을 반복한다.

프로그래머스 등대 문제 풀이 Java 소스 코드

import java.util.ArrayList;
import java.util.HashMap;

public class Solution {
	
	// 양과 늑대
	
	static int maxSheepCnt;
	static HashMap<Integer, ArrayList<Integer>> hm;
	
	public static void dfs(int currentIndex, int s, int w, ArrayList<Integer> indexList, int[] info) {
		
		if (info[currentIndex] == 0) {
			s += 1;
		} else {
			w += 1;
		}
		
		if (s <= w) return;
		
		maxSheepCnt = Math.max(maxSheepCnt, s);
		
		ArrayList<Integer> nextIndexList = new ArrayList<>();
		nextIndexList.addAll(indexList);
		
		if (hm.containsKey(currentIndex)) {
			nextIndexList.addAll(hm.get(currentIndex));
		}
		
		nextIndexList.remove(Integer.valueOf(currentIndex));
		
		for (int nextIndex : nextIndexList) {
			dfs(nextIndex, s, w, nextIndexList, info);
		}
		
		return;
	}
	
	public static int solution(int[] info, int[][] edges) {
		maxSheepCnt = 0;
		hm = new HashMap<>();
		
		for (int i = 0; i < edges.length; i++) {
			
			if (!hm.containsKey(edges[i][0])) {
				hm.put(edges[i][0], new ArrayList<>());
			}
			
			hm.get(edges[i][0]).add(edges[i][1]);
		}
		
//		hm : {0=[1, 8], 1=[2, 4], 4=[3, 6], 6=[5], 8=[7, 9], 9=[10, 11]}
		
		ArrayList<Integer> startIndexList = new ArrayList<>();
		startIndexList.add(0);
		
		dfs(0, 0, 0, startIndexList, info);
		
		return maxSheepCnt;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] info = {0,0,1,1,1,0,1,0,1,0,1,1};
		int[][] edges = {{0,1},{1,2},{1,4},{0,8},{8,7},{9,10},{9,11},{4,3},{6,5},{4,6},{8,9}};
		
		System.out.println(solution(info, edges));
	}
}

프로그래머스 양과 늑대 문제 풀이 Java 소스 코드

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

public class Solution {
	
	// 아이템 줍기
	
	public static int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
		int answer = 0;
		int[][] board = new int[101][101]; // 전체 영역
		boolean[][] visited = new boolean[101][101]; // 방문한 좌표인지 확인을 위한 2차원 boolean 배열
		int[] dx = {0, 0, -1, 1}; // 상, 하, 좌, 우 이동에서 x 좌표 증감 값
		int[] dy = {1, -1, 0, 0}; // 상, 하, 좌, 우 이동에서 y 좌표 증감 값
		
		// STEP 1. 모든 사각형의 모서리 영역과 내부 영역을 1로 채운다.
		for (int i = 0; i < rectangle.length; i++) {
			
			int[] eachRectangle = rectangle[i]; // 하나의 사각형 꼭지점 정보가 담긴 배열
			
			// 그림1의 문제를 해결하기 위해 모든 좌표 값의 크기를 2배로 해준다.
			for (int x = eachRectangle[0] * 2; x <= eachRectangle[2] * 2; x++) {
				
				for (int y = eachRectangle[1] * 2; y <= eachRectangle[3] * 2; y++) {
					board[x][y] = 1;
				}
			}
		}
		
		// STEP 2. 모서리 영역을 제외한 내부 영역을 0으로 채운다.
		for (int i = 0; i < rectangle.length; i++) {
			
			int[] eachRectangle = rectangle[i]; // 하나의 사각형 꼭지점 정보가 담긴 배열
			
			// 시작 꼭지점 좌표 + 1 ~ 마지막 꼭지점 좌표 - 1까지 0으로 채우면 사각형 내부 영역이 0으로 채워지게 된다.
			for (int x = eachRectangle[0] * 2 + 1; x <= eachRectangle[2] * 2 - 1; x++) {
				
				for (int y = eachRectangle[1] * 2 + 1; y <= eachRectangle[3] * 2 - 1; y++) {
					board[x][y] = 0;
				}
			}
		}
		
		// STEP 3. 캐릭터의 이동 정보를 담을 클래스 CharacterPosition에 캐릭터 초기값 세팅
		CharacterPosition characterPosition = new CharacterPosition(characterX * 2, characterY * 2, 0);
		
		// STEP 4. BFS 수행
		Queue<CharacterPosition> q = new LinkedList<>();
		
		q.add(characterPosition);
		
		visited[characterX * 2][characterY * 2] = true;
		
		while (!q.isEmpty()) {
			CharacterPosition tempCharacterPosition = q.poll();
			
			if (tempCharacterPosition.x == itemX * 2 && tempCharacterPosition.y == itemY * 2) { // 캐릭터가 아이템 위치에 도달했다면
				answer = tempCharacterPosition.moveCnt / 2;
				break;
			}
			
			for (int i = 0; i < 4; i++) { // 상, 하, 좌, 우 이동
				int nextX = dx[i] + tempCharacterPosition.x;
				int nextY = dy[i] + tempCharacterPosition.y;
				
				// 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다. 이 조건에 의해 2배 값인 2부터 100까지가 캐릭터의 이동 가능 범위가 된다.
				if (nextX < 2 || nextX > 100 || nextY < 2 || nextY > 100) {
					continue;
				}
				
				if (!visited[nextX][nextY] && board[nextX][nextY] == 1) { // 방문하지 않은 모서리 영역이라면
					q.offer(new CharacterPosition(nextX, nextY, tempCharacterPosition.moveCnt + 1));
					visited[nextX][nextY] = true;
				}
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] rectangle = {{1,1,7,4},{3,2,5,5},{4,3,6,9},{2,6,8,8}};
		int characterX = 1;
		int characterY = 3;
		int itemX = 7;
		int itemY = 8;
		
		// 전체 영역을 만들고, 모든 사각형의 모서리 영역과 내부 영역을 1로 채운 후, 내부 영역만 다시 0으로 채워 모서리에 남은 값 1을 따라서 좌표 이동을 하도록 만들면 된다.
		// 아래 그림1을 보면 서로 떨어져 있는 사각형이지만 두 모서리의 간격이 1이기 때문에 1을 따라서 좌표 이동을 할 경우 두 사각형이 붙어있는 것으로 인식하는 문제가 발생한다.
		// 모든 사각형의 좌표, 캐릭터의 좌표, 아이템의 좌표를 x2 하여 문제를 해결할 수 있다.
		// 이후 총 이동 거리에서 나누기 2를 해주면 된다.
		// int[][] rectangle = {{2,2,14,8},{6,4,10,10},{8,6,12,18},{4,12,16,16}};
		// int characterX = 2;
		// int characterY = 6;
		// int itemX = 14;
		// int itemY = 16;
		// 조건을 위와 같이 바꾼 후 문제를 풀고, 결과 값의 1/2을 답으로 제출하면 된다.
		
		System.out.println(solution(rectangle, characterX, characterY, itemX, itemY));
	}
}

public class CharacterPosition {
	int x = 0;
	int y = 0;
	int moveCnt = 0;
	
	public CharacterPosition(int x, int y, int moveCnt) {
		this.x = x;
		this.y = y;
		this.moveCnt = moveCnt;
	}
}

프로그래머스 아이템 줍기 문제 풀이 Java 소스 코드

public class Solution {
	
	// 피로도
	
	static int answer = 0;
	static boolean[] visited = {};
	
	public static void dfs(int depth, int k, int[][] dungeons) {
		
		for (int i = 0; i < dungeons.length; i++) {
			
			if (!visited[i] && dungeons[i][0] <= k) { // depth가 0 & 첫 번째 던전에서 dfs -> depth가 0 & 두 번째 던전에서 dfs -> depth가 0 & 세 번째 던전에서 dfs
				visited[i] = true; // 해당 던전을 방문한 상태에서 다음 depth로 dfs
				dfs(depth + 1, k - dungeons[i][1], dungeons); // depth가 1 & 위 3가지 각각의 경우에 대해 방문하지 않은 던전 dfs
				visited[i] = false; // 해당 던전으로의 dfs가 끝났으므로 다시 방문 전 상태로 변경
			}
		}
		
		answer = Math.max(answer, depth); // 몇 번째 depth까지 들어갈 수 있는지 확인
	}
	
	public static int solution(int k, int[][] dungeons) {
		visited = new boolean[dungeons.length];
		
		dfs(0, k, dungeons); // depth, 현재 피로도, 던전 배열
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int k = 80;
		int[][] dungeons = {{80,20},{50,40},{30,10}}; // 최소 필요 피로도, 소모 피로도 // {80,20} -> {30,10} -> {50,40} 가능
		
		System.out.println(solution(k, dungeons)); // 3
	}
}

프로그래머스 피로도 문제 풀이 Java 소스 코드

[Java] PCCP 모의고사 1회 외톨이 알파벳 : https://champcoder.tistory.com/80

[Java] PCCP 모의고사 1회 체육대회 : https://champcoder.tistory.com/84

[Java] PCCP 모의고사 1회 유전법칙 : https://champcoder.tistory.com/86

[Java] PCCP 모의고사 1회 운영체제 : https://champcoder.tistory.com/91

프로그래머스 PCCP 모의고사 문제 풀이 Java 소스 코드