[문제 이름 : 도둑질 (프로그래머스 42897, Lv 4)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/42897
내가 작성한 코드는 아래와 같다.
class Solution {
public int solution(int[] money) {
// int answer = Integer.MIN_VALUE;
// int len = money.length;
// for(int i=0; i<len; i++) {
// for(int j=i+2; j<len; j++) {
// if(j >= money.length) break;
// else if(i==0 && j == money.length-1) {
// continue;
// }
// answer = Math.max(answer, money[i] + money[j]);
// }
// }
// return answer;
int len = money.length;
// 첫번째 집 털고, 마지막 집 안 터는 경우
int m1 = steal(money, 0, len-2);
// 첫번째 집 안 털고, 마지막 집 터는 경우
int m2 = steal(money, 1, len-1);
// 첫번째, 마지막 모두 집 안 터는 경우
int m3 = steal(money, 1, len-2);
return Math.max(m1, Math.max(m2, m3));
}
private int steal(int[] money, int start, int end) {
// 현재 집을 털었을 때 최대 금액 & 현재 집을 털지 않았을 때 최대 금액
int include = 0, exclude = 0;
// 도둑이 털 수 있는 범위 계산
for(int i = start; i <= end; i++) {
int temp = include;
include = Math.max(include, exclude + money[i]);
exclude = temp; // 이전 집을 털었을 때 최대 금액 저장
}
return Math.max(include, exclude);
}
}
[풀이 과정]
처음 주석대로 풀이를 하니 시간초과가 나서, 다른 방법을 찾아보았다.
일반적인 배열이라면, dp[i] = max(dp[i-1], dp[i-2] + money[i])' 형태의 점화식을 사용할 것이다. 하지만, 이 문제는 원형 배열이므로 첫 번째 집과 마지막 집이 연결되어 있다. 따라서 첫 번째 집을 털 경우 마지막 집을 털 수 없고, 반대로 마지막 집을 털 경우 첫 번째 집을 털 수 없다.
1. 첫 번째 집과 마지막 집을 털지 말지 결정하는 m1,m2,m3 변수를 둔다. (주석 참고)
2. 이들은 각각 m1(첫 번째 집 털고, 마지막 집 안 털기), m2(첫 번째 집 안 털고, 마지막 집 털기), m3(첫 번째 집과 마지막 집 모두 안터기)의 값을 가지게 되고, 이들의 최대값을 구하면 된다.
3. steal() 메서드에서는 원형 배열 구조에서 도둑이 털 수 있는 집의 범위만큼 순회한다. 각각의 코드를 이해해보자.
(1). temp = include 에서 temp는 현재 집을 털지 않았을 때 금액(exclude)로 사용된다.
(2). include = Math.max(include, exclude + money[i])를 통해 현재 집을 털지 않고 넘어가는 경우 vs 현재 집을 털고 이익을 더하는 것 중 더 큰 이익을 선택한다.
(3). exclude = temp 를 통해 현재 집을 털지 않은 상태를 exclude에다가 저장한다.
풀이 시간 : 40분
다른 사람의 코드를 보니, 또다른 해법이 있어서 공유해보고자 한다.
class Solution {
public int solution(int[] money) {
int n = money.length;
int[] yfs = new int[n];
int[] nfs = new int[n];
yfs[1] = yfs[0] = money[0];
nfs[1] = money[1];
int i=2;
for(; i<n-1; i++) {
yfs[i] = Math.max(yfs[i-1], yfs[i-2] + money[i]);
nfs[i] = Math.max(nfs[i-1], nfs[i-2] + money[i]);
}
firstX[i] = Math.max(nfs[i-1], nfs[i-2] + money[i]);
return Math.max(yfs[n - 2], nfs[n - 1]);
}
}