My Dev Blog

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

import java.util.Stack;

public class Solution {
	
	// 주식가격
	
	public static int[] solution(int[] prices) {
		int[] answer = new int[prices.length];
		Stack<Integer[]> stack = new Stack<>();
		
		for (int i = 0; i < prices.length; i++) {
			answer[i] = prices.length - 1 - i; // 최대 시간으로 세팅 // 4, 3, 2, 1, 0
			Integer[] tempArr = {i, prices[i]}; // 0, 1 // 1, 2 // 2, 3 // 3, 2 // 4, 3
			
			while (!stack.isEmpty() && stack.peek()[1] > prices[i]) { // 가격이 떨어졌다면
				Integer[] price = stack.pop();
				answer[price[0]] = i - price[0];
			}
			
			stack.push(tempArr);
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] prices = {1, 2, 3, 2, 3}; // 4, 3, 1, 1, 0
		
		System.out.println(solution(prices));
	}
}

프로그래머스 주식가격 문제 풀이 Java

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	
	// 여행경로
	// 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
	// 주어진 공항 수는 3개 이상 10,000개 이하입니다.
	// 주어진 항공권은 모두 사용해야 합니다.
	// 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
	// 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
	
	static boolean[] visited;
	static ArrayList<String> travelRouteList;
	
	public static void dfs(String start, String route, String[][] tickets, int cnt) {
		if (cnt == tickets.length) {
			travelRouteList.add(route);
			return;
		}
		
		for (int i = 0; i < tickets.length; i++) {
			
			if (start.equals(tickets[i][0]) && !visited[i]) {
				visited[i] = true;
				dfs(tickets[i][1], route + " " + tickets[i][1], tickets, cnt + 1);
				visited[i] = false;
			}
		}
	}
	
	public static String[] solution(String[][] tickets) {
		String[] answer = {};
		int cnt = 0;
		visited = new boolean[tickets.length];
		travelRouteList = new ArrayList<>();
		
		dfs("ICN", "ICN", tickets, cnt);
		
		Collections.sort(travelRouteList);
		answer = travelRouteList.get(0).split(" ");
		
		for (String strRoute : answer) {
			System.out.print(strRoute + " ");
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[][] tickets = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}}; // {"ICN", "JFK", "HND", "IAD"}
//		String[][] tickets = {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}}; // {"ICN", "ATL", "ICN", "SFO", "ATL", "SFO"}
		
		System.out.println(solution(tickets));
	}
}

프로그래머스 여행경로 문제 풀이 Java