[Java] 프로그래머스 [Level-4] 도둑질

두 번째 시도(시간 초과)

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