My Dev Blog

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

import java.util.HashMap;

public class Solution {
	
	// 모음사전
	
	public static int solution(String word) {
		int answer = 0;
		
		HashMap<Character, Integer> hm = new HashMap<>();
		
		hm.put('A', 0);
		hm.put('E', 1);
		hm.put('I', 2);
		hm.put('O', 3);
		hm.put('U', 4);
		
		// A     1
		// AA    2
		// AAA   3
		// AAAA  4
		// AAAAA 5
		// AAAAE 6   (AAAAA보다 + 1) (+ 1)
		// ...
		// AAAAU 9
		// AAAE  10  (AAAA보다 + 6) (1 + 5)
		// AAAEA 11
		// AAAEU 15
		// AAAI  16
		// ...
		// AAAO  22
		// ...
		// AAAU  28
		// AAAUA 29
		// ...
		// AAAUU 33
		// AAE   34  (AAA보다 + 31) (1 + 5 + 25)
		// AAEA  35
		// AAEAA 36
		// ...
		// AAI   65
		// ...
		// AE    158 (AA보다 + 156) (1 + 5 + 25 + 125)
		// ...
		// AI    314
		// ...
		// E     782 (A보다 + 781) (1 + 5 + 25 + 125 + 625)
		// 첫 번째 자리 문자 하나가 바뀌기 위해서는 + 781(1 + 5 + 25 + 125 + 625)이 필요
		// 두 번째 자리 문자 하나가 바뀌기 위해서는 + 156(1 + 5 + 25 + 125)이 필요
		
		int[] arr = {781, 156, 31, 6, 1};
		
		answer += word.length(); // word 길이만큼 증가
		
		for (int i = 0; i < word.length(); i++) {
			answer += hm.get(word.charAt(i)) * arr[i]; // 바뀐 문자 체크하여 증가
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String word = "AAAAE";
		
		System.out.println(solution(word)); // 6
	}
}

프로그래머스 모음사전 문제 풀이 Java

public class Solution {
	
	// 정수 삼각형
	
	public static int solution(int[][] triangle) {
		int answer = 0;
		
		int[][] dpTriangle = new int[triangle.length][triangle.length];
		
		dpTriangle[0][0] = triangle[0][0];
		
		for (int i = 1; i < triangle.length; i++) {
			
			// 가장 왼쪽
			dpTriangle[i][0] = dpTriangle[i - 1][0] + triangle[i][0];
			
			// 나머지
			for (int j = 1; j < i; j++) {
				dpTriangle[i][j] = Math.max(dpTriangle[i - 1][j - 1], dpTriangle[i - 1][j]) + triangle[i][j];
			}
			
			// 가장 오른쪽
			dpTriangle[i][i] = dpTriangle[i - 1][i - 1] + triangle[i][i];
		}
		
		for (int i = 0; i < triangle.length; i++) {
			answer = Math.max(answer, dpTriangle[triangle.length - 1][i]);
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
		
		System.out.println(solution(triangle));
	}
}

프로그래머스 정수 삼각형 문제 풀이 Java

import java.util.HashMap;

public class Solution {
	
	// 다단계 칫솔 판매
	// 칫솔의 가격 100원
	// 10%를 추천인에게 주며, 원 단위에서 절사한다. 그 금액이 1원 미만인 경우 분배하지 않고 갖는다.
	
	static int[] answer = {};
	static String[] globalEnroll = {};
	static String[] globalReferral = {};
	static HashMap<String, Integer> hm;
	
	public static void RevenueShare(String member, int money) {
		int tempIndex = 0;
		int shareMoney = 0;
		
		if ("-".equals(member) || money == 0) {
			return;
		}
		
//		tempIndex = Arrays.asList(globalEnroll).indexOf(member); // 11, 12, 13 테스트케이스 시간 초과의 원인으로 확인
		tempIndex = hm.get(member); // member의 인덱스 가져오기
		
		shareMoney = money / 10;
		
		if (shareMoney < 1) { // 1원 미만인 경우 분배하지 않고 갖는다.
			answer[tempIndex] += money;
		} else {
			answer[tempIndex] += (money - shareMoney); // 90%에 해당하는 금액 더하기
			RevenueShare(globalReferral[tempIndex], shareMoney); // 추천인, 10%에 해당하는 금액으로 수익 분배
		}
	}
	
	public static int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
		answer = new int[enroll.length]; // 구성원 배열과 순서 일치
		globalEnroll = enroll; // enroll 배열은 참고에만 사용하므로 얕은 복사
		globalReferral = referral; // referral 배열은 참고에만 사용하므로 얕은 복사
		
		// STEP 1. 구성원의 인덱스 확인을 위해 HashMap 활용
		// RevenueShare 함수에서 Arrays.asList(globalEnroll).indexOf(member)를 활용해 인덱스를 가져온 결과 11, 12, 13 테스트케이스 시간초과 발생하여 HashMap 활용 방법으로 변경
		hm = new HashMap<>();
		
		for (int i = 0; i < enroll.length; i++) {
			hm.put(enroll[i], i);
		}
		
		// STEP 2. 판매자의 수익 분배
		for (int i = 0; i < seller.length; i++) {
			RevenueShare(seller[i], amount[i] * 100);
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] enroll = {"john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"}; // 구성원
		String[] referral = {"-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"}; // 구성원의 추천인
		String[] seller = {"young", "john", "tod", "emily", "mary"}; // 판매한 구성원
		int[] amount = {12, 4, 2, 5, 10}; // 판매한 개수
		
		System.out.println(solution(enroll, referral, seller, amount)); // 360, 958, 108, 0, 450, 18, 180, 1080
	}
}

<참고>

얕은 복사 : 복사된 배열이나 원본배열이 변경될 때 서로 간의 값이 같이 변경된다.
int[] a = { 1, 2, 3, 4 };
int[] b = a;

깊은 복사 : 복사된 배열이나 원본배열이 변경될 때 서로 간의 값은 바뀌지 않는다.
int[] a = { 1, 2, 3, 4 };
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++) {
	b[i] = a[i];
}

int[] a = { 1, 2, 3, 4 };
int[] b = a.clone();

int[] a = { 1, 2, 3, 4 }; 
int[] b = Arrays.copyOf(a, a.length);

int[] a = { 1, 2, 3, 4 };
int[] b = Arrays.copyOfRange(a, 1, 3);

프로그래머스 다단계 칫솔 판매 문제 풀이 Java

import java.util.*;

public class Solution {
	
	// 보석 쇼핑
	
	public static int[] solution(String[] gems) {
		int[] answer = new int[2];
		int length = Integer.MAX_VALUE;
		int startIndex = 0;
		int exceptCnt = 0;
		String tempGem = "";
		
		HashSet<String> hs = new HashSet<>(Arrays.asList(gems));
		HashMap<String, Integer> hm = new HashMap<>();
		Queue<String> q = new LinkedList<>();
		
		for (int i = 0; i < gems.length; i++) {
			hm.put(gems[i], hm.getOrDefault(gems[i], 0) + 1); // key(보석명), value(보석 개수)
			q.add(gems[i]); // 구매하려는 보석 중 제일 앞에 고른 보석과 같은 보석이 들어오게 될 경우 FIFO이 가능하도록 Queue 활용
			
			while (hm.get(q.peek()) > 1) { // 구매하려는 보석 중 제일 앞에 고른 보석이 2개 이상이 되었다면
				tempGem = q.poll(); // 제일 앞에 고른 보석 빼기
				hm.put(tempGem, hm.get(tempGem) - 1); // 해당 보석 개수 1 줄이기
				exceptCnt++; // 앞에서부터 제외할 보석 개수 증가
			}
			
			if (hm.size() == hs.size() && length > (i - exceptCnt)) { // 보석을 모두 포함하고 최소 길이라면
				length = i - exceptCnt; // 길이 갱신
				startIndex = exceptCnt + 1; // + 1을 하는 이유 : 인덱스가 아닌 몇 번째 보석인지를 return 해야 하기 때문
			}
		}
		
		answer[0] = startIndex;
		answer[1] = startIndex + length;
		
		System.out.println(answer[0] + ", " + answer[1]);
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] gems = {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};
		
		System.out.println(solution(gems)); // {3, 7}
	}
}

프로그래머스 보석 쇼핑 문제 풀이 Java

public class Solution {
	
	// 햄버거 만들기
	// 빵(1), 야채(2), 고기(3), 빵(1)일 경우 햄버거 완성
	
	public static int solution(int[] ingredient) {
		int answer = 0;
		
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < ingredient.length; i++) {
			sb.append(ingredient[i]);
			
			if (sb.length() > 3 && sb.subSequence(sb.length() - 4, sb.length()).equals("1231")) {
				sb.delete(sb.length() - 4, sb.length());
				answer++;
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] ingredient = {2, 1, 1, 2, 3, 1, 2, 3, 1};
		
		System.out.println(solution(ingredient));
	}
}

프로그래머스 햄버거 만들기 문제 풀이 Java