My Dev Blog

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

import java.util.LinkedList;

public class Solution {
	
	// [1차] 캐시
	// LRU(Least Recently Used) : 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식
	// 캐시가 가득 찼을 때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요
    
	public static int solution(int cacheSize, String[] cities) {
		int answer = 0;
		String city = "";
		
		LinkedList<String> cache = new LinkedList<>();
		
		if (cacheSize == 0) {
			return cities.length * 5;
		}
		
		for (int i = 0; i < cities.length; i++) {
			
			city = cities[i].toLowerCase();
			
			if (cache.remove(city)) { // cache hit
				cache.addFirst(city); // 제거 후 다시 추가하여 최신화
				answer += 1;
			} else { // cache miss
				
				if (cache.size() == cacheSize) {
					cache.removeLast(); // 가장 오래된 것 제거
				}
				
				cache.addFirst(city);
				answer += 5;
			}
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int cacheSize = 3;
		String[] cities = {"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};
		
		System.out.println(solution(cacheSize, cities));
	}
}

문제 해결을 위해 사용한 LinkedList에 대해 조금 더 알아보자

public void linkedListTest() {

	// add, remove(실패 시 Exception 발생), element
	// offer, poll(실패 시 null 리턴), peek
	// LinkedList의 경우 add, remove, offer, poll을 (A)로 사용해 (A), (A)First, (A)Last가 가능하다.
	// remove의 경우 remove("A")와 같이 지정 삭제가 가능하지만, poll의 경우 poll("A")와 같이 지정 삭제가 불가능하다.
		
	// 1. add & remove & element
	LinkedList<String> linkedList1 = new LinkedList<>();
		
	linkedList1.add("A"); // linkedList1.element() => A
	linkedList1.add("B"); // linkedList1.element() => A
	linkedList1.add("C"); // linkedList1.element() => A
	linkedList1.add("D"); // linkedList1.element() => A
		
	System.out.println(linkedList1.element()); // A
		
	linkedList1.remove(); // A
		
	System.out.println(linkedList1.element()); // B
		
	linkedList1.remove("C"); // C
		
	System.out.println(linkedList1.element()); // B
		
	// 2. add, addFirst, addLast & remove, removeFirst, removeLast & element
	LinkedList<String> linkedList2 = new LinkedList<>();
		
	linkedList2.add("A"); // linkedList2.element() => A
	linkedList2.addFirst("B"); // linkedList2.element() => B
	linkedList2.add("C"); // linkedList2.element() => B
	linkedList2.addLast("D"); // linkedList2.element() => B
	linkedList2.add("E"); // linkedList2.element() => B
		
	System.out.println(linkedList2.element()); // B
		
	linkedList2.removeFirst(); // B
		
	System.out.println(linkedList2.element()); // A
		
	linkedList2.removeLast(); // E
		
	linkedList2.remove("C"); // C
		
	System.out.println(linkedList2.element()); // A
		
	// 3. offer & poll & peek
	LinkedList<String> linkedList3 = new LinkedList<>();
		
	linkedList3.offer("A"); // linkedList3.peek() => A
	linkedList3.offer("B"); // linkedList3.peek() => A
	linkedList3.offer("C"); // linkedList3.peek() => A
	linkedList3.offer("D"); // linkedList3.peek() => A
		
	System.out.println(linkedList3.peek()); // A
		
	linkedList3.poll(); // A
		
	System.out.println(linkedList3.peek()); // B
		
//	linkedList3.poll("C"); // 지정 삭제 불가
		
	// 4. offer, offerFirst, offerLast & poll, pollFirst, pollLast & peek
	LinkedList<String> linkedList4 = new LinkedList<>();
		
	linkedList4.offer("A"); // linkedList4.peek() => A
	linkedList4.offerFirst("B"); // linkedList4.peek() => B
	linkedList4.offer("C"); // linkedList4.peek() => B
	linkedList4.offerLast("D"); // linkedList4.peek() => B
	linkedList4.offer("E"); // linkedList4.peek() => B
		
	System.out.println(linkedList4.peek()); // B
		
	linkedList4.pollFirst(); // B
		
	System.out.println(linkedList4.peek()); // A
		
	linkedList4.pollLast(); // E
		
//	linkedList4.poll("C"); // 지정 삭제 불가
		
	System.out.println(linkedList4.peek()); // A
}

프로그래머스 1차 캐시 문제 풀이 Java

public class Solution {
	
	// 자물쇠와 열쇠
	// key, lock 3이상 20이하 크기의 2차원 배열
	// key는 회전과 이동이 가능
	
	public static boolean openLock(int[][] checkArr, int point, int lockLength) {
		
		// point : 체크용 배열 checkArr에서 실제 lock의 시작 위치
		// lockLength : lock의 길이
		
		for (int i = 0; i < lockLength; i++) {
			
			for (int j = 0; j < lockLength; j++) {
				
				if (checkArr[point + i][point + j] != 1) return false; // 0 : 채워지지 않은 공간, 2 : 튀어나온 부분끼리 만난 공간 // lock 해제 불가
			}
		}
		
		return true;
	}
	
	public static boolean solution(int[][] key, int[][] lock) {
		int point = key.length - 1; // 2
		int checkArrSize = key.length * 2 + lock.length - 2; // 7
		
		// STEP 1. key 회전
		for (int rot = 0; rot < 4; rot++) { // 0도, 90도, 180도, 270도
			
			// STEP 2. key 이동
			for (int i = 0; i < point + lock.length; i++) { // key의 행 이동 경로
				
				for (int j = 0; j < point + lock.length; j++) { // key의 열 이동 경로
					
					// STEP 3. 체크용 배열 생성 & 자물쇠의 값 세팅
					int[][] checkArr = new int[checkArrSize][checkArrSize]; // key와 lock을 포함할 체크용 배열 생성
					
					for (int r = 0; r < lock.length; r++) {
						
						for (int c = 0; c < lock.length; c++) {
							
							checkArr[point + r][point + c] = lock[r][c]; // 체크용 배열에 lock의 값 넣기
						}
					}
					
					// STEP 4. 체크용 배열에 key의 값 추가
					for (int r = 0; r < key.length; r++) {
						
						for (int c = 0; c < key.length; c++) {
							
							if (rot == 0) { // 원본
								checkArr[i + r][j + c] += key[r][c];
							} else if (rot == 1) { // 90도 회전했을 때
								checkArr[i + r][j + c] += key[c][key.length - 1 - r];
							} else if (rot == 2) { // 180도 회전했을 때
								checkArr[i + r][j + c] += key[key.length - 1 - r][key.length - 1 - c];
							} else { // 270도 회전했을 때
								checkArr[i + r][j + c] += key[key.length - 1 - c][r];
							}
						}
					}
					
					// STEP 5. checkArr의 값을 확인해 현재 key의 위치에서 lock을 열 수 있는지 체크
					if (openLock(checkArr, point, lock.length)) return true; // lock 해제 가능하면 true 리턴
				}
			}
		}
		
		return false;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] key = {{0, 0, 0}, {1, 0, 0}, {0, 1, 1}};
		int[][] lock = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
		
		// key : 90도 회전 -> 오른쪽 한 칸 -> 아래쪽 한 칸
		
		System.out.println(solution(key, lock)); // true
	}
}

2차원 배열 시계 방향으로 90도, 180도, 270도, 360도 회전

public static int[][] rotate(int[][] arr, int degree) { // 2차원 배열 시계 방향으로 회전
	int n = arr.length;
	int m = arr[0].length;
	int[][] rotatedArr = {};
		
	// 90도 회전
	if (degree == 90) {
			
		rotatedArr = new int[m][n];
			
		for (int i = 0; i < rotatedArr.length; i++) {
				
			for (int j = 0; j < rotatedArr[i].length; j++) {
				rotatedArr[i][j] = arr[n - 1 - j][i];
			}
		}
	}
		
	// 180도 회전
	if (degree == 180) {
			
		rotatedArr = new int[n][m];
			
		for (int i = 0; i < rotatedArr.length; i++) {
				
			for (int j = 0; j < rotatedArr[i].length; j++) {
				rotatedArr[i][j] = arr[n - 1 - i][m - 1 - j];
			}
		}
	}
		
	// 270도 회전
	if (degree == 270) {
			
		rotatedArr = new int[m][n];
			
		for (int i = 0; i < rotatedArr.length; i++) {
				
			for (int j = 0; j < rotatedArr[i].length; j++) {
				rotatedArr[i][j] = arr[j][m - 1 - i];
			}
		}
	}
		
	// 360도 회전
	if (degree == 360) {
			
		rotatedArr = new int[n][m];
			
		for (int i = 0; i < rotatedArr.length; i++) {
				
			for (int j = 0; j < rotatedArr[i].length; j++) {
				rotatedArr[i][j] = arr[i][j];
			}
		}
	}
		
	return rotatedArr;
}

프로그래머스 자물쇠와 열쇠 문제 풀이 Java