My Dev Blog

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

public class Solution {

	// 숨바꼭질 - BFS 1697번
	
	static int n = 5;
	static int m = 17;
	
	public static void bfs(int a, int b) {
		Queue<Integer> q = new LinkedList<>();
		
		int[] check = new int[100001]; // 0 ~ 17까지 만들자
		boolean[] visit = new boolean[100001];
		
		Arrays.fill(check, 0); // 전체 0으로 초기화
		
		q.offer(n); //5 넣고
		visit[n] = true; // 5 방문
		
		while (!q.isEmpty()) {
			// 5 4 6 10 3 (5) 8 (5) 7 12
			// 0 1 1 1 2 0 2 0 2 2
			int num = q.poll(); // 5 꺼내 // 4 꺼내
//				check[num] = check[num] + 1;
//				visit[num] = true; // 5 방문처리 // 4 방문처리
			
			if (num == m) {
				System.out.println(check[num]);
			}
			
			if (num < 1 || num > 50000) {
				continue;
			}
			
			if (visit[num - 1] == false) { // 4를 방문하지 않았다면 // 3을 방문하지 않았다면
				q.offer(num - 1); // 4 넣기 // 3 넣기
				check[num - 1] = Math.max(check[num - 1], check[num] + 1); // check[4] = 1이 될거야 // check[3] = 2가 될거야
				visit[num - 1] = true; // 4 방문처리 // 3 방문처리
			}
			
			if (visit[num + 1] == false) { // 6을 방문하지 않았다면 // 5는 스킵
				q.offer(num + 1); // 6 넣기
				check[num + 1] = Math.max(check[num + 1], check[num] + 1); // check[6] = 1이 될거야
				visit[num + 1] = true; // 6 방문처리
			}
			
			if (visit[num * 2] == false) { // 10을 방문하지 않았다면 // 8을 방문하지 않았다면
				q.offer(num * 2); // 10 넣기 // 8 넣기
				check[num * 2] = Math.max(check[num * 2], check[num] + 1); // check[10] = 1이 될거야 // check[8] = 2가 될거야
				visit[num * 2] = true; // 10 방문 // 8 방문
			}
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 횟수의 max 카운트는 17 - 5일 거야
		// +1, -1, x2 3가지 경우에 대해 계속 bfs 수행
		bfs(n, m);
	}
}

백준 BFS 1697번 숨바꼭질

import java.util.ArrayList;

public class Solution {

	// 전쟁 - 전투 - DFS 1303번
	
	static int n = 5;
	static int m = 5;
	static char[][] arr = {{'W','B','W','W','W'}, {'W','W','W','W','W'}, {'B','B','B','B','B'}, {'B','B','B','W','W'}, {'W','W','W','W','W'}};
	static boolean[][] visit = new boolean[5][5];
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static ArrayList<Integer> wList = new ArrayList<>();
	static ArrayList<Integer> bList = new ArrayList<>();
	static int cnt = 0;
	static int wValue = 0;
	static int bValue = 0;
	
//	WBWWW
//	WWWWW
//	BBBBB
//	BBBWW
//	WWWWW
	
	public static void dfs(int i, int j) {
		
		visit[i][j] = true; // 탐색을 위해 들어왔다면 방문처리
		cnt++;
		
		for (int k = 0; k < 4; k++) {
			
			int row = i + dy[k];
			int col = j + dx[k];
			
			if (row < 0 || row > n - 1 || col < 0 || col > m - 1) {
				continue;
			}
			
			if (arr[row][col] == arr[i][j] && visit[row][col] == false) { // 팀이 같고, 아직 방문한적 없다면
				dfs(row, col);
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		for (int i = 0; i < n; i++) { // 행
			
			for (int j = 0 ; j < m; j++) { // 열
				
				if (visit[i][j] == false) { // 방문 전이라면
					cnt = 0;
					
					dfs(i, j); // 상하좌우 탐색하기 위해 dfs // 덩어리의 갯수가 결정됨
					
					if (arr[i][j] == 'W') {
						System.out.println("흰색 덩어리" + cnt);
						wList.add(cnt * cnt);
					} else if (arr[i][j] == 'B') {
						System.out.println("파란 덩어리" + cnt);
						bList.add(cnt * cnt);
					}
				}
			}
		}
		
		for (int i = 0; i < wList.size(); i++) {
			wValue += wList.get(i);
		}
		
		for (int i = 0; i < bList.size(); i++) {
			bValue += bList.get(i);
		}
		
		System.out.println("흰색 팀의 위력 : " + wValue + " 파란 팀의 위력 : " + bValue);
	}
}

백준 DFS 1303번 전쟁 - 전투

public class Solution {

	// 이동하기 - DP 11048번
	
	static int n = 3;
	static int m = 4;
	static int[][] arr = {{1, 2, 3, 4}, {0, 0, 0, 5}, {9, 8, 7, 6}};
	static int[] dy = {1, 1, 0};
	static int[] dx = {0, 1, 1};
	static int[][] dp = new int[n][m];
	
	public static void dfs(int a, int b) {
		
		for (int i = 0; i < 3; i++) {
			int ny = a + dy[i];
			int nx = b + dx[i];
			
			if (ny > n - 1 || nx > m - 1) {
				continue;
			}
			
			dp[ny][nx] = Math.max(dp[ny][nx], arr[ny][nx] + dp[a][b]);
			dfs(ny, nx); // 24, 25라인 순서 잘 생각하자 dfs는 한 번 들어가면 그대로 쭉 들어가
		}
	}
	
	public static void dynamicProgramming() {
		dp[0][0] = arr[0][0];
		dfs(0,0);
		
		for (int i = 0; i < dp.length; i++) {
			
			for (int j = 0; j < dp[i].length; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// (1,1) 좌상단에서 (N,M) 우하단까지 사탕 최대로 얻기
		dynamicProgramming();
	}
}

백준 DP 11048번 이동하기

import java.util.*;

public class Solution {

	// 보물 - Greedy 1026번
	
	public static int minVal(int n, int[] arrA, int[] arrB) {
		
		int[] arrTempA = arrA;
		
		Integer[] tempB = Arrays.stream(arrB).boxed().toArray(Integer[]::new);
		
		Arrays.sort(tempB, Collections.reverseOrder());
		
		int[] arrTempB = Arrays.stream(tempB).mapToInt(Integer::intValue).toArray();
		
		Arrays.sort(arrTempA);
		
		int numVal = 0;
		
//		for (int i = 0; i < arrTempA.length; i++) {
//			System.out.print(arrTempA[i]);
//		}
//		
//		for (int i = 0; i < arrTempB.length; i++) {
//			System.out.print(arrTempB[i]);
//		}
		
		for (int i = 0; i < n; i++) {
			numVal += (arrTempA[i] * arrTempB[i]);
		}
		
		return numVal;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		5
//		1 1 1 6 0
//		2 7 8 3 1
		// 답 18
//		int n = 5;
//		int[] arrA = {1, 1, 1, 6, 0};
//		int[] arrB = {2, 7, 8, 3, 1};
		
//		3
//		1 1 3
//		10 30 20
		// 답 80
		
		int n = 3;
		int[] arrA = {1, 1, 3};
		int[] arrB = {10, 30, 20};
		
		System.out.println(minVal(n, arrA, arrB));
	}
}

백준 Greedy 1026번 보물

public class Solution {
	
	// 쌍둥이 빌딩 숲
	// 전체 쌍둥이 빌딩의 수, 측면에서 봤을 때 보이는 빌딩의 수 [경우의 수]
	// 가장 높은 쌍둥이 빌딩부터 순서대로 배치
	// 1, 1 = 11 [1개]

	// 2, 1 = 1221, 1122 [2개] 1 * 2
	// 2, 2 = 2211 [1개] 1
	
	// 3, 1 = 133221, 123321, 122331, 122133, 133122, 113322, 112332, 112233 [8개] 2 * 4
	// 3, 2 = 233211, 223311, 221331, 221133, 331221, 331122 [6개] 1 * 4 + 2
	// 3, 3 = 332211 [1개] 1
	
	// 4, 1 = [48개] 8 * 6
	// 4, 2 = [44개] 6 * 6 + 8
	// 4, 3 = [12개] 1 * 6 + 6
	// 4, 4 = [1개] 1
	
	// 5, 1 = [384개] 48 * 8
	// 5, 2 = [400개] 44 * 8 + 48
	// 5, 3 = [140개] 12 * 8 + 44
	// 5, 4 = [20개] 1 * 8 + 12
	// 5, 5 = [1개] 1
	
	// (x, y)를 전체 쌍둥이 빌딩 x개 중, 측면에서 봤을 때 y개의 빌딩이 보이는 경우의 수라고 했을 때
	// (1, 1)은 1로 고정
	// x는 2 이상이고, y가 1일 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y) * (2 * (x - 1))
	// x는 2 이상이고, y가 1보다 크고 x보다 작을 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y) * (2 * (x - 1)) + (x - 1, y - 1)
	// x는 2 이상이고, y가 x일 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y - 1)
	
	// 11 (가장 높은 쌍둥이 빌딩 11 배치)
	// ☆☆ 1 ☆☆ 1 ☆☆ (다음으로 높은 쌍둥이 빌딩 배치할 위치 찾기)
	// 22 11 (다음으로 높은 빌딩 22를 제일 앞에 배치 시 보이는 건물 + 1, 경우의 수는 배치 전 그대로)
	// 1 22 1, 11 22 (다음으로 높은 빌딩 22를 빌딩 사이 또는 제일 뒤에 배치 시 보이는 건물 그대로, 경우의 수는 배치 전 * 2
	// 다음으로 높은 빌딩 33을 제일 앞에 배치 시 => 보이는 건물 + 1, 경우의 수는 배치 전 그대로
	// 2211(하나의 예) => 332211
	// 다음으로 높은 빌딩 33을 빌딩 사이 또는 제일 뒤에 배치 시 => 보이는 건물 그대로, 경우의 수는 배치 전 * (2 * (배치 후 쌍둥이 빌딩의 수 - 1))
	// 2211(하나의 예) => 233211, 223311, 221331, 221133
	
	// 3, 1의 경우의 수는 2, 1의 경우의 수에서만 생각 (2, 2는 이미 빌딩 2개가 보이는 상태)
	// 2, 1이 3, 1이 되기 위해서는 쌍둥이 빌딩 한 쌍을 추가로 배치하면서 보이는 건물은 그대로여야 한다. => 사이 또는 제일 뒤에 배치
	// 2, 1의 경우인 1221, 1122 경우의 수 2에 * (2 * (3 - 1)) => 3, 1 = 8개
	// 3, 2의 경우의 수는 2, 2의 경우의 수에서 사이 또는 제일 뒤에 배치, 2, 1의 경우의 수에서 제일 앞에 배치 (2가지 경우가 존재)
	// 2, 2의 경우인 2211 경우의 수 1에 * (2 * (3 - 1)) => 4
	// 2, 1의 경우인 1221, 1122 경우의 수 2 그대로
	// 3, 2 => 6개
	// 3, 3의 경우의 수는 2, 2의 경우의 수에서만 생각, 제일 앞에 배치 => 2, 2의 경우인 2211 경우의 수 1 그대로 (332211)
	
	public static int solution(int n, int count) {
		long[][] arr = new long[n + 1][n + 1];
		long preventOutOfRange = 1000000007;
		long temp = 0;
		
		arr[1][1] = 1;
		
		for (int x = 2; x <= n; x++) { // x는 2 이상
			
			for (int y = 1; y <= x; y++) {
				
				if (y == 1) { // y가 1일 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y] * (2 * (x - 1));
					temp = arr[x - 1][y] * (2 * (x - 1));
				} else if (y > 1 && y < x) { // y가 1보다 크고 x보다 작을 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y] * (2 * (x - 1)) + arr[x - 1][y - 1];
					temp = arr[x - 1][y] * (2 * (x - 1)) + arr[x - 1][y - 1];
				} else { // y가 x일 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y - 1];
					temp = arr[x - 1][y - 1];
				}
				
				arr[x][y] = temp % preventOutOfRange;
			}
		}
		
		return (int) arr[n][count];
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 3;
		int count = 1;
		
		System.out.println(solution(n, count)); // 8
	}
}

(x, y)를 전체 쌍둥이 빌딩 x개 중, 측면에서 봤을 때 y개의 빌딩이 보이는 경우의 수라고 했을 때

(1, 1)은 1로 고정

x는 2 이상이고, y가 1일 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y) * (2 * (x - 1))

x는 2 이상이고, y가 1보다 크고 x보다 작을 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y) * (2 * (x - 1)) + (x - 1, y - 1)

x는 2 이상이고, y가 x일 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y - 1)

프로그래머스 쌍둥이 빌딩 숲 문제 풀이 Java

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
	}
}

프로그래머스 순위 문제 풀이 Java

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
	}
}

프로그래머스 롤케이크 자르기 문제 풀이 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