My Dev Blog

import java.util.Arrays;

public class Solution {
	
	// 요격 시스템
	
	public static int solution(int[][] targets) {
		int answer = 0;
		
		// 개구간 (s, e)로 표현되는 폭격 미사일을 s와 e에서 발사하는 요격 미사일로는 요격할 수 없기 때문에 각각의 원소에 10을 곱한 후
		// 첫 번째 원소에서는 +1을, 두 번째 원소에서는 -1을 하여 폐구간 [r, f]을 만든 후 [Java] 프로그래머스 [Level-3] 단속카메라 문제처럼 풀도록 한다.
		int[][] tempTargets = new int[targets.length][targets[0].length];
		
		for (int i = 0; i < targets.length; i++) {
			tempTargets[i][0] = targets[i][0] * 10 + 1;
			tempTargets[i][1] = targets[i][1] * 10 - 1;
		}
		
		// int[][] targets = {{4, 5}, {4, 8}, {10, 14}, {11, 13}, {5, 12}, {3, 7}, {1, 4}};
		// int[][] tempTargets = {{41, 49}, {41, 79}, {101, 139}, {111, 129}, {51, 119}, {31, 69}, {11, 39}};
		
		// 이차원 배열 tempTargets 정렬
		Arrays.sort(tempTargets, (o1, o2) -> {
			if (o1[1] == o2[1]) { // 뒤 원소가 같을 경우
				return o1[0] - o2[0]; // 앞 원소 기준 오름차순
			} else { // 뒤 원소가 같지 않을 경우
				return o1[1] - o2[1]; // 뒤 원소 기준 오름차순
			}
		});
		
		// int[][] tempTargets = {{11, 39}, {41, 49}, {31, 69}, {41, 79}, {51, 119}, {111, 129}, {101, 139}};
		
		int missilePoint = tempTargets[0][0] - 1; // 10 // 정렬 후 첫 번째 첫 원소보다 작은 값을 넣기 위해 -1 => 최초 무조건 아래 if문에 걸리게 됨
		
		for (int i = 0; i < tempTargets.length; i++) {
			
			if (missilePoint < tempTargets[i][0]) {
				missilePoint = tempTargets[i][1];
				System.out.println(missilePoint + "번 위치에 미사일 설치");
				answer++;
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] targets = {{4, 5}, {4, 8}, {10, 14}, {11, 13}, {5, 12}, {3, 7}, {1, 4}};
		
		System.out.println(solution(targets)); // 3
	}
}

프로그래머스 요격 시스템 문제 풀이 Java

public class Solution {
	
	// 네트워크
	
	static boolean[] visited = {};
	
	public static void dfs(int i, int[][] computers) {
		visited[i] = true;
		
		for(int j = 0; j < computers[i].length; j++) {
			
			if(!visited[j] && computers[i][j] == 1) {
				dfs(j, computers);
			}
		}
	}
	
	public static int solution(int n, int[][] computers) {
		int answer = 0;
		
		visited = new boolean[n];
		
		for(int i = 0; i < n; i++) {
        	
			if(!visited[i]) {
				answer++;
				dfs(i, computers);
			}
		}
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 3; // 3대의 컴퓨터
		int[][] computers = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}; // 연결된 네트워크
		
		System.out.println(solution(n, computers)); // 2
	}
}

프로그래머스 네트워크 문제 풀이 Java

public class Solution {
	
	// 단어 변환
	
	static boolean[] visited = {};
	static int gDepth = 0;
	
	public static boolean strCompare(String str1, String str2) { // str1과 str2의 길이가 같다는 조건 하에
		int strLength = str1.length();
		int cnt = 0;
		
		for(int i = 0; i < strLength; i++) {
			
			if(str1.charAt(i) != str2.charAt(i)) {
				cnt++;
			}
		}
		
		if(cnt == 1) { // 변형 조건에서 1글자만 바꿀 수 있는데 1글자만 다를 경우
			return true;
		} else {
			return false;
		}
	}
	
	public static int dfs(String begin, String target, String[] words, int depth) { // hit // cog // {"hot", "dot", "dog", "lot", "log", "cog"}
		
		int mDepth = 0;
		
		for(int i = 0; i < words.length; i++) {
			
			mDepth = depth;
			
			if(visited[i]) {
				continue;
			}
			
			if(strCompare(begin, words[i])) { // 1글자만 다른 경우, 즉 변경 가능한 경우
				begin = words[i]; // 바꿀 단어를 비교 대상으로 변경
				mDepth++;
				visited[i] = true; // 사용한 단어 방문 처리
				
				dfs(begin, target, words, mDepth);
				
				if(begin.equals(target)) {
					System.out.println(mDepth + "번 변경으로 가능");
					gDepth = mDepth;
					break;
				}
			} else {
				continue;
			}
		}
		return gDepth;
	}
	
	public static int solution(String begin, String target, String[] words) {
		int answer = 0;
		
		visited = new boolean[words.length];
		
		answer = dfs(begin, target, words, 0);
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String begin = "hit";
		String target = "cog";
		String[] words = {"hot", "dot", "dog", "lot", "log", "cog"}; // hot -> dot -> dog -> cog
		
		System.out.println(solution(begin, target, words)); // 4
	}
}

프로그래머스 단어 변환 문제 풀이 Java

import java.util.PriorityQueue;

public class Solution {
	
	// 디펜스 게임
	
	public static int solution(int n, int k, int[] enemy) {
		int answer = enemy.length; // 모든 라운드 클리어 가능할 경우의 리턴 값
		
		PriorityQueue<Integer> pq = new PriorityQueue<>(); // 무적권을 사용해 해치울 적의 수를 남기기 위한 우선순위 큐
		
		// 디펜스 게임 시작
		for(int i = 0; i < enemy.length; i++) { // 4, 2, 4, 5, 3, 3, 1
			pq.offer(enemy[i]); // 4 // 2, 4 // 2, 4, 4 // 2, 4, 4, 5 // 3, 4, 4, 5 // 3, 4, 4, 5
			
			// 무적권은 3개이므로 pq에 4개 이상 라운드가 담기면 그중 가장 적은 적이 나타나는 라운드는 병사를 소모하여 클리어
			if(pq.size() > k) { // false // false // false // true // true // true
				n -= pq.poll(); // 7 // 7 // 7 // 5 // 2 // -1
			}
			
			if(n < 0) { // false // false // false // false // false // true
				return i; // enemy 배열의 6번째 숫자에서 음수가 나오므로 enemy 배열의 5번째 숫자까지는 pass // 5라운드까지 진출 가능
			}
		}
		
		return answer; // 여기까지 내려왔다는 것은 모든 적을 해치우고도 병사가 남았다는 얘기 즉, 모든 라운드 클리어 가능
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 7; // 병사 수
		int k = 3; // 무적권 수
		int[] enemy = {4, 2, 4, 5, 3, 3, 1}; // 라운드별 적 수
		
		System.out.println(solution(n, k, enemy)); // 5
	}
}

프로그래머스 디펜스 게임 문제 풀이 Java

public class Solution {
	
	// 숫자 타자 대회
	
	public static int[][] weight = { // 가중치
			{1, 7, 6, 7, 5, 4, 5, 3, 2, 3}, // 0에서부터 0 ~ 9까지의 가중치
			{7, 1, 2, 4, 2, 3, 5, 4, 5, 6}, // 1에서부터 0 ~ 9까지의 가중치
			{6, 2, 1, 2, 3, 2, 3, 5, 4, 5}, // 2에서부터 0 ~ 9까지의 가중치
			{7, 4, 2, 1, 5, 3, 2, 6, 5, 4}, // 3에서부터 0 ~ 9까지의 가중치
			{5, 2, 3, 5, 1, 2, 4, 2, 3, 5}, // 4에서부터 0 ~ 9까지의 가중치
			{4, 3, 2, 3, 2, 1, 2, 3, 2, 3}, // 5에서부터 0 ~ 9까지의 가중치
			{5, 5, 3, 2, 4, 2, 1, 5, 3, 2}, // 6에서부터 0 ~ 9까지의 가중치
			{3, 4, 5, 6, 2, 3, 5, 1, 2, 4}, // 7에서부터 0 ~ 9까지의 가중치
			{2, 5, 4, 5, 3, 2, 3, 2, 1, 2}, // 8에서부터 0 ~ 9까지의 가중치
			{3, 6, 5, 4, 5, 3, 2, 4, 2, 1}  // 9에서부터 0 ~ 9까지의 가중치
	};
	public static int[][][] dp; // depth, 왼손 손가락 위치, 오른손 손가락 위치
	public static String targetNumbers; // numbers
	public static int targetDepth; // numbers의 depth
	
	public static int contest(int depth, int lPos, int rPos) {
		
		if (depth == targetDepth + 1) { // targetDepth를 넘었다면
			return 0;
		}
		
		if (dp[depth][lPos][rPos] != 0) { // 이미 구한 값이라면
			return dp[depth][lPos][rPos];
		}
		
		int targetPos = targetNumbers.charAt(depth) - '0'; // 1 // 7 // 5 // 6
		int result = Integer.MAX_VALUE;
		
		// 왼손 손가락으로 누르기
		if (targetPos != rPos) { // 오른손 손가락으로 바로 누를 수 있는 상황(오른손 손가락으로 눌렀을 때 최소 가중치가 보장되는 상황)이 아니라면, 왼손 손가락으로 눌러보기
			result = Math.min(contest(depth + 1, targetPos, rPos) + weight[lPos][targetPos], result);
		}
		
		// 오른손 손가락으로 누르기
		if (targetPos != lPos) { // 왼손 손가락으로 바로 누를 수 있는 상황(왼손 손가락으로 눌렀을 때 최소 가중치가 보장되는 상황)이 아니라면, 오른손 손가락으로 눌러보기
			result = Math.min(contest(depth + 1, lPos, targetPos) + weight[rPos][targetPos], result);
		}
		
		dp[depth][lPos][rPos] = result;
		
		return dp[depth][lPos][rPos];
	}
	
	public static int solution(String numbers) {
		targetNumbers = numbers; // "1756"
		targetDepth = numbers.length() - 1; // 3
		
		dp = new int [targetDepth + 1][10][10]; // 0 ~ 3 // 0 ~ 9 // 0 ~ 9
		
		return contest(0, 4, 6); // 초기 depth 0, 초기 왼손 손가락 위치 4, 초기 오른손 손가락 위치 6
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String numbers = "1756"; // 0 ~ 3 depth
		
		System.out.println(solution(numbers)); // 10
	}
}

프로그래머스 숫자 타자 대회 문제 풀이 Java

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