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 그림을 보면서 이해해 보자

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

 

 

공격 & 4이므로 첫 번째 값은 -4 하단과 우측 값은 4 우측 하단 값은 -4로 설정한다.

 

상하 누적 합의 범위는 N행(여기서는 4행)까지이므로 파란색 부분은 대상에서 제외

 

좌우 누적 합의 범위는 M열(여기서는 5열)까지이므로 파란색 부분은 대상에서 제외

 

 

 

 

 

 

 

 

 

 

 

프로그래머스 파괴되지 않은 건물 문제 풀이 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

<최대 연속 부분 수열의 합>

public class Solution {
	
	// 최대 연속 부분 수열의 합
	// 현재 합, 합의 최대값 갱신
	// 1. 수의 합을 반복적으로 구한다.
	// 2. 이 때 합이 음수이면 그 다음 수부터 다시 시작
	// 3. 합의 최대값을 도출
	
	public static int getMaxSubsequence(int[] arr) {
		int temp = 0;
		int max = 0;
		
		for (int i = 0; i < arr.length; i++) {
			temp += arr[i];
			
			if (temp > max) {
				max = temp;
			} else if (temp < 0) {
				temp = 0;
			}
		}
		
		return max;
	}
	
	public static int getMaxElementForNegativeArr(int[] arr) { // 배열의 원소가 전부 음수일 경우
		int max = -10000;
		
		for (int i = 0; i < arr.length; i++) {
			
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		
		return max;
	}

	public static int solution(int[] arr) {
		
		int result = getMaxSubsequence(arr);
		
		if (result != 0) {
			return result;
		} else { // result 값이 0이라는 건 배열의 원소가 모두 음수라는 얘기
			return getMaxElementForNegativeArr(arr);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {-3, 3, 5, -3, -7, 9, -2, 10, -5, -2};
		// 0 번째 -3 : 현재 합 0, 합의 최대값 0
		// 1 번째 3 : 현재 합 3, 합의 최대값 3 (0보다 크므로 갱신)
		// 2 번째 5 : 현재 합 8, 합의 최대값 8 (3보다 크므로 갱신)
		// 3 번째 -3 : 현재 합 5, 합의 최대값 8 (갱신되지 않음)
		// 4 번째 -7 : 현재 합 0 (else if 조건문에 의해 -2 -> 0), 합의 최대값 8 (갱신되지 않음)
		// 5 번째 9 : 현재 합 9, 합의 최대값 9 (8보다 크므로 갱신)
		// 6 번째 -2 : 현재 합 7, 합의 최대값 9 (갱신되지 않음)
		// 7 번째 10 : 현재 합 17, 합의 최대값 17 (9보다 크므로 갱신)
		// 8 번째 -5 : 현재 합 12, 합의 최대값 17 (갱신되지 않음)
		// 9 번째 -2 : 현재 합 10, 합의 최대값 17 (갱신되지 않음)
		
		System.out.println(solution(arr)); // 합의 최대값 17
	}
}

최대 연속 부분 수열의 합 알고리즘 문제 풀이 Java

 

플로이드 워셜 알고리즘

다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.

 

public class FloydWarshall {
	
	// 플로이드 워셜 알고리즘
	// 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
	// 만약 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘을 사용해야 한다.
	
	static int number = 4;
	static int INF = 100000000;
	static int[][] originArr = {{0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0}}; // 자료 배열 초기화
	
	public static void floydWarshall() {
		int[][] renewArr = new int[number][number]; // 결과 배열 초기화
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				renewArr[i][j] = originArr[i][j]; // 결과 배열을 초기 자료 배열과 동일하게 만들어 준다.
			}
		}
		
		// k : 거쳐가는 노드
		for (int k = 0; k < number; k++) {
			
			// i : 출발 노드
			for (int i = 0; i < number; i++) {
				
				// j : 도착 노드
				for (int j = 0; j < number; j++) {
					
					if (renewArr[i][k] + renewArr[k][j] < renewArr[i][j]) { // k 노드를 거쳐갈 때 거리 값이 더 작다면
						renewArr[i][j] = renewArr[i][k] + renewArr[k][j]; // i 노드에서 j 노드로 가는 최단 거리 갱신
					}
				}
			}
		}
		
		for (int i = 0; i < number; i++) {
			
			for (int j = 0; j < number; j++) {
				System.out.print(renewArr[i][j] + " "); // 결과 배열 출력
			}
			
			System.out.println();
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		floydWarshall();
	}
}

Floyd Warshall 알고리즘 문제 풀이 Java

<우선순위 큐를 활용한 풀이>

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

public class DijkstraByPriorityQueue {
	
	public static int n = 6; // 노드의 개수
	public static int INF = 1000000; // 무한대를 의미
	public static HashMap<Integer, ArrayList<Node>> nodeListMap = new HashMap<>(); // key : 각 노드의 인덱스(0 ~ 5), value : 각 노드의 인덱스로부터 전체 노드까지의 인덱스와 거리를 담을 리스트
	public static HashMap<Integer, Integer> minDistanceMap = new HashMap<>(); // key : 각 노드의 인덱스(0 ~ 5), value : 각 노드까지의 최단거리(출발 노드로부터)
	
	public static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐 생성 // 출발 노드로부터 현재 최단거리에 있는 노드부터 우선적으로 빼내어 체크하기 위함(출발 노드로부터 현재 최단거리에 있는 노드를 체크해야 다른 노드들까지의 최단거리 갱신의 가능성이 있기 때문)
		Node pqNode; // 우선순위 큐에서 빼낸 노드를 담을 변수(출발 노드로부터 현재 최단거리에 있는 노드)
		ArrayList<Node> nodeList; // 우선순위 큐에서 빼낸 (출발 노드로부터 현재 최단거리)노드를 거쳐서 체크할 타겟 노드 리스트

		// 각 노드까지의 최단거리 초기화
		for (int key : nodeListMap.keySet()){ // 0 ~ 5
			minDistanceMap.put(key, INF); // 모든 최단거리 무한대로 초기화
		}
        
		minDistanceMap.put(start, 0); //출발 노드까지의 최단거리는 0으로 SET
        
		pq.add(new Node(start, 0)); // 출발 노드를 우선순위 큐에 추가 // 최단거리가 갱신되었으므로 우선순위 큐에 추가 => 이 최단거리를 거쳐 다른 노드들까지의 최단거리도 갱신될 수 있기 때문

		while (!pq.isEmpty()) { // 더 이상 최단거리 갱신이 불가할 때까지 반복

			pqNode = pq.poll(); // 출발 노드로부터 현재 최단거리에 있는 노드

			if (pqNode.getDistance() > minDistanceMap.get(pqNode.getIndex())) { // 최단거리 갱신이 가능한지 체크
				continue;
			}
            
			nodeList = nodeListMap.get(pqNode.getIndex()); // 현재 최단거리에 있는 노드를 거쳐서 체크할 타겟 노드 리스트
            
			for (Node node : nodeList) { // 타겟 노드 0 ~ 5 모두 체크
                
				if (pqNode.getDistance() + node.getDistance() < minDistanceMap.get(node.getIndex())) { // 출발 노드로부터 현재 최단거리에 있는 노드를 거쳐서 타겟 노드로 가는 거리가 타겟 노드의 최단거리보다 작을 경우
					minDistanceMap.put(node.getIndex(), pqNode.getDistance() + node.getDistance()); // 타겟 노드의 최단거리 갱신
					pq.add(new Node(node.getIndex(), pqNode.getDistance() + node.getDistance())); // 타겟 노드 우선순위 큐에 추가
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 0; i < n; i++) { // 0 ~ 5
			nodeListMap.put(i, new ArrayList<Node>()); // key값 0 ~ 5(각 노드 인덱스)마다 Node 정보를 담을 리스트 생성
		}
		
		nodeListMap.get(0).add(new Node(0, 0)); // 0번 노드로부터 0번 노드까지의 거리 0
		nodeListMap.get(0).add(new Node(1, 2)); // 0번 노드로부터 1번 노드까지의 거리 2
		nodeListMap.get(0).add(new Node(2, 5)); // 0번 노드로부터 2번 노드까지의 거리 5
		nodeListMap.get(0).add(new Node(3, 1)); // 0번 노드로부터 3번 노드까지의 거리 1
		nodeListMap.get(0).add(new Node(4, INF)); // 0번 노드로부터 4번 노드까지의 거리 INF
		nodeListMap.get(0).add(new Node(5, INF)); // 0번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(1).add(new Node(0, 2)); // 1번 노드로부터 0번 노드까지의 거리 2
		nodeListMap.get(1).add(new Node(1, 0)); // 1번 노드로부터 1번 노드까지의 거리 0
		nodeListMap.get(1).add(new Node(2, 3)); // 1번 노드로부터 2번 노드까지의 거리 3
		nodeListMap.get(1).add(new Node(3, 2)); // 1번 노드로부터 3번 노드까지의 거리 2
		nodeListMap.get(1).add(new Node(4, INF)); // 1번 노드로부터 4번 노드까지의 거리 INF
		nodeListMap.get(1).add(new Node(5, INF)); // 1번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(2).add(new Node(0, 5)); // 2번 노드로부터 0번 노드까지의 거리 5
		nodeListMap.get(2).add(new Node(1, 3)); // 2번 노드로부터 1번 노드까지의 거리 3
		nodeListMap.get(2).add(new Node(2, 0)); // 2번 노드로부터 2번 노드까지의 거리 0
		nodeListMap.get(2).add(new Node(3, 3)); // 2번 노드로부터 3번 노드까지의 거리 3
		nodeListMap.get(2).add(new Node(4, 1)); // 2번 노드로부터 4번 노드까지의 거리 1
		nodeListMap.get(2).add(new Node(5, 5)); // 2번 노드로부터 5번 노드까지의 거리 5
		
		nodeListMap.get(3).add(new Node(0, 1)); // 3번 노드로부터 0번 노드까지의 거리 1
		nodeListMap.get(3).add(new Node(1, 2)); // 3번 노드로부터 1번 노드까지의 거리 2
		nodeListMap.get(3).add(new Node(2, 3)); // 3번 노드로부터 2번 노드까지의 거리 3
		nodeListMap.get(3).add(new Node(3, 0)); // 3번 노드로부터 3번 노드까지의 거리 0
		nodeListMap.get(3).add(new Node(4, 1)); // 3번 노드로부터 4번 노드까지의 거리 1
		nodeListMap.get(3).add(new Node(5, INF)); // 3번 노드로부터 5번 노드까지의 거리 INF
		
		nodeListMap.get(4).add(new Node(0, INF)); // 4번 노드로부터 0번 노드까지의 거리 INF
		nodeListMap.get(4).add(new Node(1, INF)); // 4번 노드로부터 1번 노드까지의 거리 INF
		nodeListMap.get(4).add(new Node(2, 1)); // 4번 노드로부터 2번 노드까지의 거리 1
		nodeListMap.get(4).add(new Node(3, 1)); // 4번 노드로부터 3번 노드까지의 거리 1
		nodeListMap.get(4).add(new Node(4, 0)); // 4번 노드로부터 4번 노드까지의 거리 0
		nodeListMap.get(4).add(new Node(5, 2)); // 4번 노드로부터 5번 노드까지의 거리 2
		
		nodeListMap.get(5).add(new Node(0, INF)); // 5번 노드로부터 0번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(1, INF)); // 5번 노드로부터 1번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(2, 5)); // 5번 노드로부터 2번 노드까지의 거리 5
		nodeListMap.get(5).add(new Node(3, INF)); // 5번 노드로부터 3번 노드까지의 거리 INF
		nodeListMap.get(5).add(new Node(4, 2)); // 5번 노드로부터 4번 노드까지의 거리 2
		nodeListMap.get(5).add(new Node(5, 0)); // 5번 노드로부터 5번 노드까지의 거리 0
		
		dijkstra(0); // 출발 노드 0
		
		for (int i = 0; i < n; i++) { // 0 ~ 5
			System.out.print(minDistanceMap.get(i) + " "); // 각 노드까지의 최단거리 출력(출발 노드로부터)
		}
	}
}
public class Node implements Comparable<Node> {
	
	private int index = 0; // 노드의 번호
	private int distance = 0; // 노드의 거리
	
	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}
	
	public int getIndex() {
		return this.index;
	}
	
	public int getDistance() {
		return this.distance;
	}

	@Override
	public int compareTo(Node otherNode) {
		// TODO Auto-generated method stub
		return this.distance - otherNode.distance; // distance 기준 오름차순 정렬 // 1, 2, 3, ...
//		return otherNode.distance - this.distance; // distance 기준 내림차순 정렬 // ..., 3, 2, 1
	}
}

 

출력 결과 : 0 2 3 1 2 4

 

Dijkstra(다익스트라) 알고리즘 우선순위 큐 문제 풀이 Java

'Algorithm > Dijkstra' 카테고리의 다른 글

[Algorithm] Dijkstra-1  (0) 2022.11.27

+ Recent posts