My Dev Blog

import java.util.Arrays;

public class Solution {
	
	// 구명보트
	
	public static int solution(int[] people, int limit) {
		int answer = 0;
		
		Arrays.sort(people); // 50, 50, 70, 80
		
		int maxWeightIndex = people.length - 1; // 구조되지 않은 사람 중 가장 무거운 무게를 가진 사람의 인덱스
		int minWeightIndex = 0; // 구조되지 않은 사람 중 가장 가벼운 무게를 가진 사람의 인덱스
		
		for (int i = maxWeightIndex; i >= 0; i--) { // 구조되지 않은 사람 중 가장 무거운 무게를 가진 사람부터 순서대로 구조
			
			answer++; // 보트에 타지 못하는 경우는 없으므로 1 증가 // 구조되지 않은 사람 중 가장 무거운 무게를 가진 사람 무조건 보트에 태우기
			
			if (i == minWeightIndex) { // max 인덱스 감소 후 min 인덱스와 값이 같다는 것은 해당 위치에 혼자 남은 경우를 의미하며 위에서 구조 보트에 이미 탔기 때문에(answer증가) 바로 break
				break;
			}
			
			if (people[i] + people[minWeightIndex] <= limit) { // 보트에는 최대 2명까지 탈 수 있고 구조되지 않은 사람 중 가장 무거운 무게를 가진 사람이 탄 보트에 현재 가장 가벼운 사람 또한 함께 탈 수 있다면
				minWeightIndex++; // 현재 가장 가벼운 사람도 함께 구조된 것으로 간주하고 min 인덱스 1 증가 => 다음 가벼운 사람에게 순서를 넘김
			}
			
			if (i == minWeightIndex) { // min 인덱스 증가 후 max 인덱스와 값이 같다면 모든 인원에 대해 구조가 끝난 상황이므로 바로 break
				break;
			}
			
//			if (i <= minWeightIndex) { // 위에 break if문 2개를 모두 주석처리 하고 이 if문만 살려도 결과는 같다.
//				break;
//			}
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] people = {70, 50, 80, 50};
		int limit = 100;
		
		System.out.println(solution(people, limit));
	}
}

프로그래머스 구명보트 문제 풀이 Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
	
	// 행렬과 연산
	// Deque 자료구조에서
	// add(A) + peek(B) or remove(B)가 있을 때 // (A)와 (B)는 First 또는 Last
	// (A)와 (B)가 같다면 스택(Stack)처럼 동작
	// (A)와 (B)가 다르다면 큐(Queue)처럼 동작
	// addFirst로 쌓고 있는 구조에서 제일 앞에 원소를 추가하고 싶다면 addLast로 추가
	// addLast로 쌓고 있는 구조에서 제일 앞에 원소를 추가하고 싶다면 addFirst로 추가
	
	static int r = 0; // rc의 행 수
	static int c = 0; // rc의 열 수
	static Deque<Integer> firstCol; // rc의 1열
	static Deque<Integer> lastCol; // rc의 마지막열
	static Deque<Deque<Integer>> restRows; // rc의 1열, 마지막열을 제외한 나머지 행들
	
	// 2차원 배열을 2개의 열과 나머지 행 구조로 나누기
	public static void rcSetting(int[][] rc) {
		r = rc.length; // 행
		c = rc[0].length; // 열
		firstCol = new ArrayDeque<Integer>(); // 1열
		lastCol = new ArrayDeque<Integer>(); // 마지막열
		restRows = new ArrayDeque<Deque<Integer>>(); // 나머지 행
		
//		1 2 3
//		4 5 6
//		7 8 9
		
//		2차원 배열이 위와 같다면
//		r = 3, c = 3
//		firstCol = {1, 4, 7}
//		lastCol = {3, 6, 9}
//		restRows = {2, 5, 8}
		
		// 상단, 좌측부터 addFirst로 넣을 거야
		// 모두 addFirst로 넣는다는 것을 기억
		for (int i = 0; i < r; i++) {
			firstCol.addFirst(rc[i][0]); // 1열 담기
			lastCol.addFirst(rc[i][c - 1]); // 마지막열 담기
			
			 Deque<Integer> tempRow = new ArrayDeque<Integer>(); // restRows에 담을 tempRow 생성
			 
			 for (int j = 1; j < c - 1; j++) { // 1열과 마지막열을 제외한 모든 열의 원소 담기
				 tempRow.addFirst(rc[i][j]);
			 }
			 
			 restRows.addFirst(tempRow); // tempRow 담기
		}
	}
	
	// 테두리 한 칸씩 시계방향 회전
	public static void rotate() {
		
		if (c == 2) { // firstCol, lastCol만으로 이루어진 2차원 배열
			lastCol.addLast(firstCol.removeLast());
			// firstCol의 제일 처음에 들어왔던 원소가 빠져나가야 함 => addFirst에서 Queue 구조로 빠져나가려면 removeLast로 빼내야 한다.
			// 빼낸 값을 lastCol의 addFirst로 제일 처음 들어왔던 원소보다 앞에 넣어야 하므로 addLast로 넣어준다.
			
			firstCol.addFirst(lastCol.removeFirst());
			// lastCol의 제일 마지막에 들어왔던 원소가 빠져나가야 함 => addFirst에서 Stack 구조로 빠져나가려면 removeFirst로 빼내야 한다.
			// 빼낸 값을 firstCol의 addFirst로 가장 마지막에 들어왔던 원소의 뒤에 넣어야 하므로 똑같이 addFirst로 넣어준다.
			
			return;
		}
		
		// 테두리에 원소 추가할 순서는 상, 우, 하, 좌 순서로 하겠다.
		restRows.peekLast().addLast(firstCol.removeLast()); // 1열(firstCol)의 처음 들어온 원소를 빼냄(addFirst에서 Queue 구조로 쓰기 위해 removeLast) => restRows의 처음 들어온 행을 기준으로 잡아야 함(Queue 구조로 쓰기 위해 peekLast) => 행의 원소 중 처음에 들어왔던 원소보다 앞에 넣어줘야 하므로 addLast
		lastCol.addLast(restRows.peekLast().removeFirst()); // restRows의 처음 들어온 행 중 마지막 원소를 빼내어 마지막 열 제일 앞에 끼어들기해서 추가
		restRows.peekFirst().addFirst(lastCol.removeFirst()); // 마지막 열의 제일 마지막에 들어온 원소를 빼내어 restRows의 가장 마지막에 들어온 행 중 가장 마지막에 들어온 원소 뒤에 추가
		firstCol.addFirst(restRows.peekFirst().removeLast()); // restRows의 가장 마지막에 들어온 행 중 처음 들어온 원소를 빼내어 1열 제일 마지막에 들어온 원소 뒤에 추가
	}
	
	// 행 한 칸씩 아래로 이동
	public static void shiftRow() {
		// 가장 마지막에 들어온 행 또는 원소를 가장 처음 위치에 넣어줘야 한다. addFirst 추가 구조이므로 스택 구조로 빼내기 위해 removeFirst, 제일 앞에 추가해줘야 하므로 addLast를 써준다.
		restRows.addLast(restRows.removeFirst()); // 행
		firstCol.addLast(firstCol.removeFirst()); // 1열
		lastCol.addLast(lastCol.removeFirst()); // 마지막열
	}
	
	public static int[][] solution(int[][] rc, String[] operations) {
		int[][] answer = {};
        
		// STEP 1. 2차원 배열 rc => 2개의 열과 나머지 행 구조로 나누기
		rcSetting(rc);
        
		// STEP 2. 메인 작업
		for (String operation : operations) { // "Rotate", "ShiftRow"
        	
			switch (operation.charAt(0)) { // 'R', 'S'
				case 'R' : rotate(); break;
				case 'S' : shiftRow(); break;
			}
		}
        
		// STEP 3. 2차원 배열 answer에 값 담기
		answer = new int[r][c];
        
		for (int i = 0; i < r; i++) {
			// addFirst 추가 구조에서 큐 구조로 빼내기 위해 removeLast 사용
			answer[i][0] = firstCol.removeLast(); // 1열
			answer[i][c - 1] = lastCol.removeLast(); // 마지막열
        	
			Deque<Integer> tempRow = new ArrayDeque<Integer>(); // restRows의 각 행을 담기 위해 tempRow 생성
        	
			// addFirst 추가 구조에서 큐 구조로 빼내기 위해 removeLast 사용
			tempRow = restRows.removeLast();
        	
			for (int j = 1; j < c - 1; j++) {
				answer[i][j] = tempRow.removeLast();
			}
		}
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] rc = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
		String[] operations = {"Rotate", "ShiftRow"}; // Rotate : 행렬 바깥쪽에 있는 원소를 시계 방향으로 회전, ShiftRow : 행을 한 칸씩 아래로 이동
		
//		    Rotate  ShiftRow
//		1 2 3    4 1 2    8 9 6
//		4 5 6    7 5 3    4 1 2
//		7 8 9    8 9 6    7 5 9
		
		System.out.println(solution(rc, operations)); // {{8, 9, 6}, {4, 1, 2}, {7, 5, 3}}
	}
}

Deque 자료구조에 대해 어느 정도 학습이 된 후 풀이하는 것을 추천한다.

프로그래머스 행렬과 연산 문제 풀이 Java

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

public class Solution {
	
	// 두 큐 합 같게 만들기
	
	public static int solution(int[] queue1, int[] queue2) {
		int answer = 0;
		int length = queue1.length;
		long queue1Sum = 0; // queue1의 합계만을 사용할 것
		long totalSum = 0;
		long targetSum = 0;
		
		Queue<Integer> q1 = new LinkedList<>();
		Queue<Integer> q2 = new LinkedList<>();
        
		queue1Sum = Arrays.stream(queue1).sum(); // 6
        
		totalSum = queue1Sum + Arrays.stream(queue2).sum(); // 20

		if (totalSum % 2 == 1) return -1; // 똑같이 나눌 수 없다면 -1 리턴
        
		targetSum = totalSum / 2; // 10 // 하나의 큐만 절반 값을 맞춘다면 okay, 절반 값을 이용
        
		for (int i = 0; i < length; i++) {
			q1.offer(queue1[i]); // 1, 2, 1, 2
			q2.offer(queue2[i]); // 1, 10, 1, 2
		}
        
		int tempNum = 0;
        
		while (queue1Sum != targetSum) {
        	
			if (queue1Sum < targetSum) {
				tempNum = q2.poll();
				q1.offer(tempNum);
				queue1Sum += tempNum;
			} else {
				tempNum = q1.poll();
				q2.offer(tempNum);
				queue1Sum -= tempNum;
			}
        	
			answer++;
        	
			// queue1, queue2의 모든 원소가 자리바꿈하여 다시 원래의 위치로 오기 위한 횟수 (queue1.length + queue2.length) * 2 = 16
			// 즉 16이 된다는 것은 다시 처음의 경우와 같아졌음을 의미하고, 더이상 반복할 필요가 없음을 뜻한다.
			if (answer > length * 4 - 1) return -1;
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] queue1 = {1, 2, 1, 2};
		int[] queue2 = {1, 10, 1, 2};
		
		System.out.println(solution(queue1, queue2)); // 7
	}
}

프로그래머스 두 큐 합 같게 만들기 문제 풀이 Java

import java.util.*;

public class Solution {
	
	//	성격 유형 검사하기
	
	static String[] typeArr = {"RT", "CF", "JM", "AN"};
	
	public static String typeCheck(HashMap<Character, Integer> hm) {
		
		StringBuilder sb = new StringBuilder();
		
		char firstChar;
		char secondChar;
		char typeChar;
		
		for (String s : typeArr) { // "RT", "CF", "JM", "AN"
			
			firstChar = s.charAt(0); // 'R', 'C', 'J', 'A'
			secondChar = s.charAt(1);// 'T', 'F', 'M', 'N'
			
			typeChar = hm.get(firstChar) >= hm.get(secondChar) ? firstChar : secondChar;
			
			sb.append(typeChar); // 'T' + 'C' + 'M' + 'A'
		}
		
		return sb.toString(); // "TCMA"
	}
	
	public static String solution(String[] survey, int[] choices) {
		String answer = "";
		int[] score = {0, 3, 2, 1, 0, -1, -2, -3}; // choices 값에 따라 점수 부여
		
		HashMap<Character, Integer> hm = new HashMap<>(); // 타입, 점수 담을 HashMap
		
		int scoreSum = 0; // 타입별 점수를 담을 변수
		
		for (String s : typeArr) { // "RT", "CF", "JM", "AN"
			hm.put(s.charAt(0), 0); // 'R' : 0, 'C' : 0, 'J' : 0 ,'A' : 0
			hm.put(s.charAt(1), 0); // 'T' : 0, 'F' : 0, 'M' : 0 ,'N' : 0
		}
		
		for (int i = 0; i < survey.length; i++) { // "AN", "CF", "MJ", "RT", "NA"
			// 'A' 스코어 // 'C' 스코어 // 'M' 스코어 // 'R' 스코어 // 'N' 스코어 업데이트
			scoreSum = hm.get(survey[i].charAt(0)) + score[choices[i]];
			hm.put(survey[i].charAt(0), scoreSum);
		}
		
		// 'R' : -3, 'C' : 1, 'J' : 0 ,'A' : -1
		// 'T' :  0, 'F' : 0, 'M' : 2 ,'N' : -1
		answer = typeCheck(hm);
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] survey = {"AN", "CF", "MJ", "RT", "NA"}; // survey 원소의 첫 글자를 기준으로 점수를 부여할 것이므로 score = {0, 3, 2, 1, 0, -1, -2, -3}으로 세팅
		int[] choices = {5, 3, 2, 7, 5}; // A : += score[5] // C : += score[3] // M : += score[2] // R : += score[7] // N : += score[5]
		
		System.out.println(solution(survey, choices));
	}
}

프로그래머스 성격 유형 검사하기 문제 풀이 Java

두 번째 시도(시간 초과)

public class Solution {
	
	// 도둑질 // 두 번째 시도(시간 초과)
	
	public static int getMaxMoneyExceptTargetIndex(int[] money, int targetIndex) {
		int[] dp = new int[money.length - 1]; // 제일 먼저 1을 뺐을 경우 2,3,1,4,2,5에서 개미전사 문제
		int num1 = (targetIndex + 1) % (money.length); // 타겟 인덱스의 바로 다음 인덱스
		int num2 = (targetIndex + 2) % (money.length); // 타겟 인덱스의 다음 다음 인덱스
		int num3 = 0;
		
		dp[0] = money[num1];
		dp[1] = money[num2];
		
		for (int i = 2; i < money.length - 1; i++) {
			num3 = (targetIndex + i + 1) % (money.length);
			dp[i] = Math.max(dp[i - 2] + money[num3], dp[i - 1]);
		}
		
		return dp[money.length - 2];
	}
	
	public static int solution(int[] money) {
		int answer = 0;
		int maxMoney = 0;
        
		for (int i = 0; i < money.length; i++) {
			maxMoney = Math.max(maxMoney, getMaxMoneyExceptTargetIndex(money, i)); // i번째 인덱스를 제외했을 때의 최대 값
		}
        
		answer = maxMoney;
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] money = {1, 2, 3, 1, 4, 2, 5}; // 1 빼고 2,3,1,4,2,5 개미전사 문제 // 2 빼고 3,1,4,2,5,1 개미전사 문제 // 3 빼고 1,4,2,5,1,2 개미전사 문제 // 총 7개의 값 중 max값을 return
		
		System.out.println(solution(money));
	}
}

첫 번째 시도(★ 부분으로 인해 예외 발생)

세 번째 시도 성공

public class Solution {
	
	// 도둑질
	// 첫 번째 시도(★ 부분으로 인해 예외 발생)
	// 세 번째 시도 성공
	
	public static int solution(int[] money) {
		int answer = 0;
		int[] dpExceptLast = new int[money.length - 1]; // 1, 2, 3, 1, 4, 2 담자
		int[] dpExceptFirst = new int[money.length - 1]; // 2, 3, 1, 4, 2, 5 담자
        
		dpExceptLast[0] = money[0]; // 1
//		dpExceptLast[1] = money[1]; // 2 // ★ 첫 번째 풀이에서 예외가 발생했던 이유 !
		dpExceptLast[1] = Math.max(money[0], money[1]); // 2 // 이게 맞지
		
		dpExceptFirst[0] = money[1]; // 2
//		dpExceptFirst[1] = money[2]; // 3 // ★ 첫 번째 풀이에서 예외가 발생했던 이유 !
		dpExceptFirst[1] = Math.max(money[1], money[2]); // 3 // 이게 맞지
        
		for (int i = 2; i < money.length; i++) {
			if (i < money.length - 1) {
				dpExceptLast[i] = Math.max(dpExceptLast[i - 2] + money[i], dpExceptLast[i - 1]);
			}
        	
			if (i > 2) {
				dpExceptFirst[i - 1] = Math.max(dpExceptFirst[i - 3] + money[i], dpExceptFirst[i - 2]);
			}
		}
        
		answer = Math.max(dpExceptLast[money.length - 2], dpExceptFirst[money.length - 2]);
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] money = {1, 2, 3, 1, 4, 2, 5};
		
		System.out.println(solution(money));
	}
}

프로그래머스 도둑질 문제 풀이 Java

public class Solution {
	
	// 파괴되지 않은 건물
	
	public static int solution(int[][] board, int[][] skill) {
		int answer = 0;
		int[] arr = new int[skill[0].length];
		int startRowNum = 0;
		int startColNum = 0;
		int endRowNum = 0;
		int endColNum = 0;
		int affectPoint = 0;
        
		for (int i = 0; i < skill.length; i++) {
			arr = skill[i];
        	
			startRowNum = arr[1];
			startColNum = arr[2];
			endRowNum = arr[3];
			endColNum = arr[4];
        	
			affectPoint = (arr[0] == 1 ? -arr[5] : arr[5]);
        	
			for (int j = startRowNum; j <= endRowNum; j++) {
        		
				for (int z = startColNum; z <= endColNum; z++) {
					board[j][z] += affectPoint;
				}
			}
		}
        
		for (int j = 0; j < board.length; j++) {
    		
			for (int z = 0; z < board[j].length; z++) {
//				System.out.print(board[j][z] + " ");
				if (board[j][z] > 0) answer++;
			}
//			System.out.println();
		}
		
	return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] board = {{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5}}; // 4개의 행 5개의 열
		int[][] skill = {{1,0,0,3,4,4},{1,2,0,2,3,2},{2,1,0,3,1,2},{1,0,1,3,3,1}}; // 1은 공격, 2는 회복 // {1,0,0,3,4,4}는 공격이며 0행0열 ~ 3행4열까지 4의 피해를 준다는 의미
		
		System.out.println(solution(board, skill)); // 10
	}
}

시간 초과 발생

<누적합 이용한 문제 풀이>

public class Solution {
	
	// 파괴되지 않은 건물
	
	public static int solution(int[][] board, int[][] skill) {
		int answer = 0;
		int N = board.length;
		int M = board[0].length;
		int[][] sumArr = new int[N+1][M+1];
		int[] infoArr = new int[skill[0].length];
		int startRowNum = 0;
		int startColNum = 0;
		int endRowNum = 0;
		int endColNum = 0;
		int affectPoint = 0;
        
		for (int i = 0; i < skill.length; i++) {
			infoArr = skill[i];
        	
			startRowNum = infoArr[1];
			startColNum = infoArr[2];
			endRowNum = infoArr[3];
			endColNum = infoArr[4];
        	
			affectPoint = (infoArr[0] == 1 ? -infoArr[5] : infoArr[5]);
        	
			sumArr[startRowNum][startColNum] += affectPoint; // 좌상 +
			sumArr[startRowNum][endColNum + 1] += -affectPoint; // 좌하 -
			sumArr[endRowNum + 1][startColNum] += -affectPoint; // 우상 -
			sumArr[endRowNum + 1][endColNum + 1] += affectPoint; // 우하 +
		}
        
        
		// 상하의 합
		for (int i = 1; i < N; i++) {
        	
			for (int j = 0; j < M; j++) {
				sumArr[i][j] += sumArr[i - 1][j];
			}
		}
        
		// 좌우의 합
		for (int j = 1; j < M; j++) {
        	
			for (int i = 0; i < N; i++) {
				sumArr[i][j] += sumArr[i][j - 1];
			}
		}
        
		for (int i = 0; i < N; i++) {
        	
			for (int j = 0; j < M; j++) {
        		
				if (board[i][j] + sumArr[i][j] > 0) {
					answer++;
				}
			}
		}
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] board = {{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5}}; // 4개의 행 5개의 열
		int[][] skill = {{1,0,0,3,4,4},{1,2,0,2,3,2},{2,1,0,3,1,2},{1,0,1,3,3,1}}; // 1은 공격, 2는 회복 // {1,0,0,3,4,4}는 공격이며 0행0열 ~ 3행4열까지 4의 피해를 준다는 의미
		
		System.out.println(solution(board, skill)); // 10
	}
}

1 ~ 11 그림을 보면서 이해해 보자

중간에 번호가 붙지 않은 예시는 이해를 돕기 위한 설명이니 신경쓰지 않아도 된다.

프로그래머스 파괴되지 않은 건물 문제 풀이 Java

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

public class Solution {
	
	// 주차 요금 계산
	
	public static int calcMin(String time1, String time2) {
		String[] time1Arr = time1.split(":");
		String[] time2Arr = time2.split(":");
		
		int min = (Integer.parseInt(time2Arr[0]) * 60 + Integer.parseInt(time2Arr[1])) - (Integer.parseInt(time1Arr[0]) * 60 + Integer.parseInt(time1Arr[1]));
		
		return min;
	}
	
	public static int[] solution(int[] fees, String[] records) {
		int[] answer = {};
		String[] tempArr = new String[3];
        
		// 차량 번호로 기록 구분 필요
		// 0000 : 06:00 IN, 06:34 OUT, 18:59 IN, 23:59 OUT // 34 + 300
		// 0148 : 07:59 IN, 19:09 OUT // 670
		// 5961 : 05:34 IN, 07:59 OUT, 22:59 IN, 23:00 OUT // 145 + 1
		// IN과 OUT은 담을 필요없다. 기록이 짝수 개 존재하는 것이 중요하며, 이 문제에서는 무조건 IN, OUT, IN, OUT 순서이다.
        
		HashMap<String, ArrayList<String>> hmlist = new HashMap<>();
		ArrayList<String> numberList = new ArrayList<>();
        
		for (int i = 0; i < records.length; i++) {
			tempArr = records[i].split(" "); // "06:00", "0000", "IN"
        	
			if (!hmlist.containsKey(tempArr[1])) { // "0000"
				hmlist.put(tempArr[1], new ArrayList<String>()); // key 등록 // "0000"
        		
				numberList.add(tempArr[1]); // key값만 담아둘 리스트 // "0000"
			}
        	
			hmlist.get(tempArr[1]).add(tempArr[0]); // "06:00"
		}
        
        // numberList에 현재 넘버 리스트 담겨있음
        
        Collections.sort(numberList); // key값 리스트 오름차순 정렬
        
        for (String str : numberList) { // 0000, 0148, 5961
        	
        	System.out.println(str);
        	
        	if (hmlist.get(str).size() % 2 == 1) { // 짝이 안맞는다면, 즉 마지막 출차 기록이 없다면
        		hmlist.get(str).add("23:59"); // 마지막 출차 기록은 23:59로
        	}
        }
        
        int[] totalTimeArr = {}; // 차량 번호별 총 시간 담기 위한 배열
        
        totalTimeArr = new int[numberList.size()]; // 시간 담을 배열 크기는 차량 번호 수만큼
        answer = new int[numberList.size()]; // 금액 담을 배열 크기는 차량 번호 수만큼
        
        String[] tempTimeArr = new String[2]; // 시간 두 개씩 잘라서 분으로 바꾸기 위한 임시 배열
        
        int j = 0; // 차량 번호 수만큼 증가시킬 변수
        
        for (String str : numberList) {
        	
        	int i = 0; // 시간 두 개를 담기 위한 인덱스 i
        	int timeSum = 0;
        	
        	for (String time : hmlist.get(str)) {
        		tempTimeArr[i] = time; // 0, 1
        		i++;
        		
        		if (i == 2) { // 0, 1을 넘어가면
        			timeSum += calcMin(tempTimeArr[0], tempTimeArr[1]); // 분 계산 함수
        			i = 0; // 시간 두 개씩 끊기 위해 0으로 초기화
        		}
        	}
        	
        	totalTimeArr[j] = timeSum; // 해당 차량 번호의 총 시간
        	j++; // 0 ~ 2
        }
        
        double d = 0;
        
        for (int i = 0; i < totalTimeArr.length; i++) {
        	
        	if (totalTimeArr[i] <= fees[0]) { // 180분을 넘지 않았다면
        		answer[i] = fees[1]; // 5000원
        	} else { // 180분을 초과했다면
        		d = (double)(totalTimeArr[i] - fees[0]) / fees[2]; // 소수점 올림을 위해 double형으로 받기
        		answer[i] = (int)Math.ceil(d) * fees[3] + fees[1]; // 초과한 금액 + 5000원
        	}
        }
        
        for (int i = 0; i <answer.length; i++) {
        	System.out.println(answer[i]);
        }
        
        return answer;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] fees = {180, 5000, 10, 600}; // 기본시간(분), 기본요금(원), 단위시간(분), 단위요금(원)
		String[] records = {"05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"}; // 시:분 차 번호 IN/OUT // 마지막 나간 기록 없으면 23:59 나간 것으로 간주
		
		System.out.println(solution(fees, records)); // 14600, 34400, 5000
	}
}

프로그래머스 주차 요금 계산 문제 풀이 Java

첫 시도에서 런타임 에러가 발생해 다른 방법으로 풀이하였다.

import java.util.HashSet;

public class Solution {
	
	// 등대
	
	public static int solution(int n, int[][] lighthouse) {
		int answer = 0;
		int[] linkedCntArr; // 각 등대에 연결된 등대의 수를 입력받기 위한 배열
		
		HashSet<Integer> edgeHs = new HashSet<>(); // 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대의 번호를 담을 HashSet
		HashSet<Integer> turnOnHs = new HashSet<>(); // 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된, 반드시 켜야 하는 등대의 번호를 담을 HashSet
		int[][] remainingLightHouse; // 반드시 켜야 하는 등대를 킨 후 남은 등대 쌍을 담을 2차원 배열
		int remainingCnt; // remainingLightHouse에 담긴 등대 쌍의 수
		
		// CASE 1을 기준으로 설명
		
		for (int a = 0; a < n; a++) { // 과정 반복
			
			// 현재 turnOnHs가 비어있지 않은 상황이라면, turnOnHs에 담긴 번호의 등대를 킨 상황으로, 켜진 등대의 영향을 받는 등대는 고려해야 할 대상에서 제외한다.(lighthouse의 길이가 줄었을 것)
			
			linkedCntArr = new int[n + 1]; // linkedCntArr 초기화 // 0 ~ n
			remainingLightHouse = new int[lighthouse.length][2]; // remainingLightHouse 초기화
			remainingCnt = 0; // remainingCnt 초기화
			
			for (int i = 0; i < lighthouse.length; i++) {
				linkedCntArr[lighthouse[i][0]]++;
				linkedCntArr[lighthouse[i][1]]++;
			}
			
			// linkedCntArr : {0, 4, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 3, 1, 1}
			
			for (int i = 0; i < linkedCntArr.length; i++) {
				
				if (linkedCntArr[i] == 1) { // 연결된 등대가 하나뿐이라면 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대
					edgeHs.add(i); // edgeHs에 등대 번호 담기
				}
			}
			
			// edgeHs : [3, 4, 7, 8, 11, 13, 14]
			
			for (int i = 0; i < lighthouse.length; i++) {
				
				// 가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된 등대 번호를 turnOnHs에 담기 // 반드시 켜야 하는 등대 번호
				
				if (edgeHs.contains(lighthouse[i][0]) || edgeHs.contains(lighthouse[i][1])) {
					
					if (edgeHs.contains(lighthouse[i][0])) {
						turnOnHs.add(lighthouse[i][1]);
					} else {
						turnOnHs.add(lighthouse[i][0]);
					}
				}
			}
			
			// turnOnHs : [1, 6, 10, 12]
			
			for (int i = 0; i < lighthouse.length; i++) {
				
				// turnOnHs에 담긴 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍이 있는지 확인
				
				if (!turnOnHs.contains(lighthouse[i][0]) && !turnOnHs.contains(lighthouse[i][1])) {
					remainingLightHouse[remainingCnt] = lighthouse[i];
					remainingCnt++;
				}
			}
			
			// remainingLightHouse : {{2, 9}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}
			// remainingCnt == 1
			
			if (remainingCnt == 0) { // 현재 켜진 등대로 모든 등대를 밝힐 수 있다면
				break;
			}
			
			if (remainingCnt == 1) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍이 1쌍 존재한다면
				answer += 1; // 남은 1쌍의 등대 중 어떤 등대를 켜도 되기 때문에 1만 증가
				break;
			}
			
			if (remainingCnt < lighthouse.length) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍의 수가 2 이상 lighthouse.length 미만이라면
				lighthouse = new int[remainingCnt][2]; // lighthouse의 길이 줄이기
				
				for (int i = 0; i < remainingCnt; i++) { // 현재 켜진 등대의 영향으로 밝힐 수 없는 등대 쌍만 고려하면 된다.
					lighthouse[i] = remainingLightHouse[i];
				}
			}
			
			// 다시 for문으로 가 과정 반복
		}
		
		answer += turnOnHs.size(); // 켜진 등대의 수를 더해준다.
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// CASE 1
		int n = 14;
		int[][] lighthouse = {{4, 1}, {5, 1}, {5, 6}, {7, 6}, {1, 2}, {1, 3}, {6, 8}, {2, 9}, {9, 10}, {10, 11}, {5, 12}, {12, 13}, {12, 14}};
		// CASE 2
//		int n = 10;
//		int[][] lighthouse = {{4, 1}, {5, 1}, {5, 6}, {7, 6}, {1, 2}, {1, 3}, {6, 8}, {2, 9}, {9, 10}};
		// CASE 3
//		int n = 8;
//		int[][] lighthouse = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {5, 6}, {5, 7}, {5, 8}};
		
		System.out.println(solution(n, lighthouse));
	}
}

2022.11.17 기준 정답률이 6%밖에 안되는 문제이기 때문일까? 점수를 13점이나 준다.

내가 풀이한 방법은 이렇다.

STEP 1. 반드시 켜야 하는 등대의 기준

가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대와 연결된 등대는 반드시 켜야 한다.

가장자리(둘레나 끝에 해당되는 부분)에 위치한 등대는 lighthouse 배열의 원소들 중 하나만 존재하는 번호에 해당하며,

그 번호와 쌍을 이루는 번호는 반드시 켜야 하는 등대의 번호를 의미한다.

STEP 2. 반드시 켜야 하는 등대의 번호를 HashSet에 담고, lighthouse 배열의 원소들 중 HashSet에 존재하는 번호가

있을 경우, 그 번호를 포함한 등대 쌍(배열)을 제거한다. => 현재 켜진 등대로 밝힐 수 없는 등대 쌍만 남게 된다.

STEP 3. STEP 2에서 남은 등대 쌍으로 lighthouse 배열을 다시 만든다.

STEP 4. STEP 1부터 과정을 반복한다.

프로그래머스 등대 문제 풀이 Java