(25.01.29)
문제 이해
- 이웃한 집을 털지 않고 훔칠 수 있는 최대의 돈을 반환하라.
문제 접근
문제 접근 1
쉬워보이면서도 어려워 보이는 문제이다. 그 이유는, 쉽게만 생각하면 하나씩 띄엄띄엄 훔친 뒤 인덱스 0에서 시작한 돈과 인덱스 1에서 시작한 돈에서 최댓값을 구하면 참 좋겠지만 앞선 문제에서처럼 1 1 100 1 처럼 극단적인 돈의 차이가 있을 수 있기에 이전 문제와 같이 누적최소비용 배열을 만드는 방법으로 접근해보면 좋을 듯 하다. 다만 주의할 점은 이전 문제와 달리 꼭 끝까지 도달하지 않아도 된다는 점이 있지만, 돈은 훔칠 수록 좋으니(돈은 0이상임) 기존의 계획대로 접근해보도록 하자.
class Solution {
public int rob(int[] nums) {
int length=nums.length;
int[] accumulated_cost=new int[length];
accumulated_cost[length-1]=nums[length-1];
for(int i=length-2; i>=0; i--){
accumulated_cost[i]+=accumulated_cost[i+1]+nums[i];
}
return accumulated_cost[0];
}
}막상 코드를 작성해보니 인접한 집을 털면 안된다는 조건을 고려하지 않았다.
그러나 이를 고려하는 방법이 마땅히 생각나지 않는다. 한 칸을 건너 뛸 수도, 두 칸을 건너 뛸 수도 있다. 모든 경우를 확인하는 방법도 있겠지만 이는 TLE가 발생할 것 같기 때문에..
문제 접근 2
문제대로 이웃한 집을 고려하기에는 복잡하니 반대로 이웃한 집만 고려해보면 어떨까? 뭔가 이웃한 집의 값을 뺀 것을 저장하고.. 잘 쓰면 될 것 같기도 한데..? 아니면 최댓값 순서대로 접근해보면서 이웃한거만 피해가면 어떨까? 이 방법을 사용하게 되면
case 1) input=[1,2,3,1]에서 3+1=4로 통과이다
case 2) input=[2,7,9,3,1]에서 9+2+1=12로 통과이다.
위 방법이 모든 케이스를 전부 담을 수는 없을 것 같지만 우선 시도해보자.
class Solution {
public int rob(int[] nums) {
int length=nums.length;
if(length==2){
return Math.max(nums[0], nums[1]);
} else if(length==3){
return Math.max(nums[1], nums[0]+nums[2]);
}
Integer[][] indexedArray=new Integer[length][2];
for(int i=0; i<length; i++){
indexedArray[i][0]=nums[i];
indexedArray[i][1]=i;
}
Arrays.sort(indexedArray, (a,b)->Integer.compare(b[0],a[0]));
boolean[] visited=new boolean[length];
int max_val=indexedArray[0][0], prev_index=indexedArray[0][1];
visited[prev_index]=true;
for(int i=1; i<length; i++){
int cur_index=indexedArray[i][1];
if(cur_index==0 && !visited[cur_index] && cur_index+1<length &&!visited[cur_index+1]){
visited[cur_index]=true;
max_val+=indexedArray[i][0];
}
if(cur_index==length-1 && !visited[cur_index] && cur_index-1>=0 &&!visited[cur_index-1]){
visited[cur_index]=true;
max_val+=indexedArray[i][0];
}
if(!visited[cur_index] && cur_index-1>=0 && cur_index+1<length && !visited[cur_index-1] &&!visited[cur_index+1]){
visited[cur_index]=true;
max_val+=indexedArray[i][0];
}
}
return max_val;
}
}
최대한 위 방법으로 예외처리만 추가해서 해결해보려했지만.. 코드가 제대로 작동을 안하는 것 같다. 보다 좋은 if문 조건과 디버깅으로 추후 오류를 수정해보자.
(25.02.09)
큐큐 오늘 조금이라도 하자! 문제 기억도 안나니 이해부터.
대충 이웃은 털지 못하고 최대로 훔칠 수 있는 금액의 합.
문제 접근 3
만약 공간을 조금 이용해서 각 위치 별로 얻을 수 있는 금액+양옆에 잃는 금액을 표시한 배열을 만든다면 이용할 수 있을까?
[1,2,3,1]의 경우 [1-2, 2-4, 3-3, 1-1]=[-1,-2,1,0]을 만들 수 있고.. 큰 비용의 순서대로 접근하며 겹치지 않게 고른다면 1을 고르고 -1을 골라 실제 값인 1+3=4가 나온다.
[2,7,9,3,1]의 경우 [-5, -4, -3, -7, -2]가 되고 -2와 -3과 -5를 골라 2+9+1=12가 된다. 답이 나오네?
위를 알고리즘으로 구현해보자.
class Solution {
public int rob(int[] nums) {
int length=nums.length;
if(length==1)//간단한 케이스 처리
return nums[0];
else if (length==2) {
return Math.max(nums[0], nums[1]);
}
int[][] relative_nums=new int[length][2];
relative_nums[0][0]=nums[0]-nums[1];
relative_nums[length-1][0]=nums[length-1]-nums[length-2];
relative_nums[0][1]=0;
relative_nums[length-1][1]=length-1;
for(int i=1; i<length-1; i++){
relative_nums[i][0]+=nums[i]-(nums[i-1]+nums[i+1]);
relative_nums[i][1]=i;
}
Arrays.sort(relative_nums, Comparator.comparingInt(n -> -n[0]));
int max_money=0;
boolean[] visited=new boolean[length];
for(int i=0; i<length; i++){
int cur_idx=relative_nums[i][1];
if(is_available(visited, cur_idx)){
max_money+=nums[cur_idx];
visited[cur_idx]=true;
}
}
return max_money;
}
private boolean is_available(boolean[] visited, int index){
if(visited[index]){//이미 접근한 곳을 확인하지 않는 로직으로 호출해야 한다.
System.out.println("ERROR!");
return false;
}
if(index==0){
if(visited[index+1])
return false;
else
return true;
} else if(index==visited.length-1){
if(visited[index-1])
return false;
else
return true;
}
if(visited[index-1]||visited[index+1])
return false;
return true;
}
}
제출하기 전 기존에 통과하지 못한 케이스들을 우선적으로 돌려봤는데, 마찬가지로 [1,7,9,4]에서 7+4가 아닌 9+1을 고르는 문제를 발견하였다.
내 알고리즘을 따르면 상대배열이 [-6, -3, -2, -5]기에 7이 아닌 9를 선택하게 된다.
(25.02.13)
가능하면 GPT나 힌트를 자제해보자. 문제를 다시 생각해보면 이웃하지 않고 최대의 돈을 훔치는 것. 그나저나 왜 모든 경우를 따져보는건 생각을 안해봤을까?
length에서 이웃하지 않고 방문할 수 있는 최대의 가구 수는 짝수일 때 length/2, 홀수일 때 length/2+1이다.(4가구면 2, 5가구면 3) 이를 MAX_VISIT으로 두자.
그럼 이를 인덱스 추출의 관점으로 봐서 1~MAX_VISIT까지 가능한 모든 금액들을 계산한다고 보자.
다만 각 VISIT별 어떻게 인덱스를 골라야하는지 이웃하지 않아야 한다는 것을 고려하기 쉽지 않아 보인다.. 하지만 쉽게 생각해서 그냥 전체를 탐색하고 이웃한 경우만 continue되게 하면..? 이거 백트레킹 쓰면 될거같은데.. 사실 잘 기억이 안난다.. 공부가 많이 부족했구나..
그리고 백트레킹이란 개념 외에 재귀개념이 정말 많이 쓰인다는 걸 느낄 수 있디...
아 진짜 간단하게 어떻게 이 문제를 엄청 쉽게 간파할 수 있는 방법 없을까?
그리고 아무리 생각해도 내가 위에 접근한 방법들이 정말 깔끔하게 잘 접근한 것 같은데.. 최적화 시도를 해보자.
우선 주석을 이용해 정리해보았다.
class Solution {
public int rob(int[] nums) {
int length=nums.length;
//간단한 케이스 처리
if(length==1)// 숫자가 하나일 때
return nums[0];
else if (length==2) {// 숫자가 두개일 때
return Math.max(nums[0], nums[1]);
}
//이웃 원소만큼을 뺀 상대 값을 저장하는 배열. 또한 기존의 인덱스 위치까지 포함하여 2차원으로 저장한다.
int[][] relative_nums=new int[length][2];
//양 끝 값 Index Out of Range 오류 방지로 직접 입력
relative_nums[0][0]=nums[0]-nums[1];
relative_nums[length-1][0]=nums[length-1]-nums[length-2];
relative_nums[0][1]=0;
relative_nums[length-1][1]=length-1;
//현재 값에서 이웃한 값을 뺀다.
for(int i=1; i<length-1; i++){
relative_nums[i][0]+=nums[i]-(nums[i-1]+nums[i+1]);
relative_nums[i][1]=i;
}
//내림차순 정렬
Arrays.sort(relative_nums, Comparator.comparingInt(n -> -n[0]));
int max_money=0;
boolean[] visited=new boolean[length];
for(int i=0; i<length; i++){//모든 원소에 대하여 차례로(상대 값이 큰 순서대로 접근)
int cur_idx=relative_nums[i][1];//현재 원소의 기존 인덱스
if(is_available(visited, cur_idx)){//접근 가능한지 확인(방문처리된 위치로 부터 이웃해 있지 않은지 여부
max_money+=nums[cur_idx];//최댓값에 가산
visited[cur_idx]=true;//방문처리
}
}
return max_money;
}
private boolean is_available(boolean[] visited, int index){
if(visited[index]){//이미 접근한 곳을 확인하지 않는 로직으로 호출해야 한다.
System.out.println("ERROR!");
return false;
}
if(index==0){
if(visited[index+1])
return false;
else
return true;
} else if(index==visited.length-1){
if(visited[index-1])
return false;
else
return true;
}
if(visited[index-1]||visited[index+1])
return false;
return true;
}
}문제접근 3에서 문제가 되었던 테스트 케이스인 1,7,9,4를 핸들링 하기 위해 루프로 감싸 최댓값 뿐 아닌 그보다 작은 값을 최댓값으로 가지는 경우를 고려하게 하였다.
int max_money=0;
boolean[] visited=new boolean[length];
for(int start=0; start<length; start++) {//최댓값을 포함하지 않는 경우까지 고려하기 위함.
int money=0;
for (int i = start; i < length; i++) {//모든 원소에 대하여 차례로(상대 값이 큰 순서대로 접근)
int cur_idx = relative_nums[i][1];//현재 원소의 기존 인덱스
if (is_available(visited, cur_idx)) {//접근 가능한지 확인(방문처리된 위치로 부터 이웃해 있지 않은지 여부
money += nums[cur_idx];//최댓값에 가산
visited[cur_idx] = true;//방문처리
}
}
if(money>max_money)
max_money=money;
for(int i=0; i<length; i++){//방문 초기화
visited[i]=false;
}
//System.out.println(money);
}
(25.02.21)
지난번에 코드를 알맞게 수정했는데 테스트에 걸렸던 것 까지 기억난다. 내 기억 상 코드는 충분히 문제를 해결할 수 있는 로직이었던 걸로 기억하기에 디버깅을 시도해보자.
디버깅
현재 문제가 되는 케이스는 {4,1,2,7,5,3,1}이다. 이 케이스에서는 기존에 1칸씩 건너뛰던 방식과 달리 가장 큰 수인 7을 선택하고 좌측으로 1과 2를 건너뛰어 4를 선택하고 우측으론 3을 선택하여 4+7+3=14가 된다.
하지만 현재 내 코드상에서는 4 7 1을 고른다. 여기서 구현의도와 다른 점이 발견됐는데, 나는 가장 큰 수를 우선적으로 고르게끔 설정했기에 7, 4, 3 순서대로 골라야 정상이다.
논리 오류를 찾아냈다. 내 코드는 단순히 가장 큰 수부터 고르는 것이 아닌 relative_nums 즉 양 옆에 이웃한 수를 뺀 값을 기반으로 정렬했다. 그 결과 7은 relative_nums에서 7-(5+2)로 0인 반면, 4-(1)으로 3인 맨 첫 원소 4가 우선권을 가진다.
그렇다면 relative_nums가 아닌 일반적으로 큰 수를 우선적으로 뽑고 다음으로 큰 수를 뽑으며 계산한 전체 금액 중 가장 큰 값을 선정하면 문제를 해결할 수 있을까? 테스트 케이스로 계산을 해보자.
solution.test(solution.rob(new int[]{1,2,3,1})
, 4);
solution.test(solution.rob(new int[]{2,7,9,3,1})
, 12);
solution.test(solution.rob(new int[]{2,3,2})
, 4);
solution.test(solution.rob(new int[]{1,7,9,4})
, 11);
solution.test(solution.rob(new int[]{1,2,3,1})
, 4);
solution.test(solution.rob(new int[]{4,1,2,7,5,3,1})
, 14);3+1=4
9+2+1=12
2+2=4
7+4=11
3+1=4
7+4+3=14
로 가능할 듯 하다. 코드로 구현시켜보자. 중요한 점은 사용할 가장 큰 수를 순차적으로 내려가며 계산한다는 점이다.
https://github.com/choijiwoong/LeetCode/commit/265c41f24bf52dcc512997634884be709ef79360
51/70까지 진행할 수 있었다. 우선 테스트 케이스 업데이트 후 문제점을 확인해보자.
public static void main(String[] args){
Solution solution=new Solution();
solution.test(solution.rob(new int[]{1,2,3,1})
, 4);
solution.test(solution.rob(new int[]{2,7,9,3,1})
, 12);
solution.test(solution.rob(new int[]{2,3,2})
, 4);
solution.test(solution.rob(new int[]{1,7,9,4})
, 11);
solution.test(solution.rob(new int[]{1,2,3,1})
, 4);
solution.test(solution.rob(new int[]{4,1,2,7,5,3,1})
, 14);
solution.test(solution.rob(new int[]{8,9,9,4,10,5,6,9,7,9})
, 44);
}{8,9,9,4,10,5,6,9,7,9}에서 큰 값 기준으로 10-9-9-9, 9-9-9-5-4, 9-9-9-8-5로 40이 선택됐다. 이상적인 답은 10-9-9-9-8로 45가 된다. 즉, 10에서 제대로 탐색이 안됬다. 이유는 같은 수이기 때문에 문제가 생긴 것 같기에 수가 같은 경우 모두 탐색(원래도 되어야하는데??)하게끔 디버깅하면 될 듯 하다.
(25.02.28)
아니 한달을 붙잡고 있었네..?
현재 문제가 발생한 부분은 정렬 후 큰 수부터 차례로 선택하게하여 계산하는 부분에서 같은 수의 경우도 정렬이 되는 부분이다. 이로 인해 같은 숫자이지만 크고 작음을 구분하여 처리하는 문제가 있다.
문제 접근 4
즉, 값이 같은 수의 경우를 고려해야한다. int[][] 형식의 sorted_nums을 사용하는 경우엔 정렬 시 같은 수 순서가 발생하는 것은 불가피 하기에 정렬 방식을 바꿔야 할 것 같다.
입력으로 넘어온 nums를 set으로 만들어 모든 원소에 대해 큰수별로 접근하면서 같은 수의 경우도 처리하면 어떨까?
최대한 기억나는 백트레킹을 이용하여 접근해보려했는데, 같은 수의 경우..가 역시 문제인 것 같다..
문제 접근 5
최대한 간단하게 생각해보자. 다시 처음으로 돌아가자.
문제는 큰 돈만 털면된다. 조건은 하나다 이웃한 집을 털지 말것. 모든 경우를 찾아내기만 하면 큰 돈이 얼마인지 계산하는 것은 쉽다. 이웃한 집을 방문하는 모든 경우의 수를 찾아내는게 키포인트이다.
int {1,2,3,4,5}가 있다 해보자. 경우는 1개를 고를 경우, 2개를 경우, 3개를 고를 경우가 있다. 1개를 고르면 4개는 고르지 않는거고, 2개를 고르면 3개를 고르지 않는거고, 3개를 고르면 2개를 고르지 않는거다. 확통의 개념과 비슷하다. 조합은 5!/2!*3!처럼 경우의 수를 계산할 수 있다. 그럼 이 순서는 어떻게 계산하는가?
최대한 간단히 생각해보자. 배열의 양 옆에 원소 -1을 추가하면
int {1}은 에서 1을 고를 경우 {-1,1,-1}로 이웃 원소 접근을 막음을 표시할 수 있다.
위 경우 최대는 양 옆은 뺀 1이된다.
int {1,2}은 1을 고르면 {-1,1,-1,-1}이 되어 1이 된다.
2를 고르면 {-1,-1,2,-1}이 되어 2가 된다.
int {1,2,3}은 1고르면 {-1,1,-1,3,-1}로 4
2를 고르면 {-1,-1,2,-2,-1}로 2
3을 고르면 {-1,1,-1,3,-1}로 4
1,3을 고르면 {-1,1,-1,3,-2}로 4가 된다.
GPT를 이용한 문제 해결
아 어렵당!!! 아무리봐도 백트레킹밖에 생각이 안나는데 어케 적용하는지, 그리고 같은 수의 경우 어떻게 처리할지 모르겠다. GPT선생님을 불러서 내 코드의 피드백을 요청해보자. 현재까지의 코드는 아래와 같다.
//백업
class Solution {
public int rob(int[] nums) {
int length=nums.length;
//간단한 케이스 처리
if(length==1)// 숫자가 하나일 때
return nums[0];
else if (length==2) {// 숫자가 두개일 때
return Math.max(nums[0], nums[1]);
}
//sort by big num with origin index
int[][] sorted_nums=new int[length][2];
for(int i=0; i<length; i++){
sorted_nums[i][0]=nums[i];
sorted_nums[i][1]=i;
}
Arrays.sort(sorted_nums, Comparator.comparingInt(n->-n[0]));
int max_money=0;
boolean[] visited=new boolean[length];
for(int start=0; start<=length/2; start++) {
int money=0;
for (int i = start; i < length; i++) {//모든 원소에 대하여 차례로(상대 값이 큰 순서대로 접근)
int cur_idx = sorted_nums[i][1];//현재 원소의 기존 인덱스
if (is_available(visited, cur_idx)) {//접근 가능한지 확인(방문처리된 위치로 부터 이웃해 있지 않은지 여부
money += nums[cur_idx];//최댓값에 가산
visited[cur_idx] = true;//방문처리
//System.out.print(nums[cur_idx]);
}
}
if(money>max_money)
max_money=money;
for(int i=0; i<length; i++){
visited[i]=false;
}
//System.out.println(money);
}
return max_money;
}
private boolean is_available(boolean[] visited, int index){
if(visited[index]){//이미 접근한 곳을 확인하지 않는 로직으로 호출해야 한다.
System.out.println("ERROR!");
return false;
}
if(index==0){
if(visited[index+1])
return false;
else
return true;
} else if(index==visited.length-1){
if(visited[index-1])
return false;
else
return true;
}
if(visited[index-1]||visited[index+1])
return false;
return true;
}
public void test(long answer, long result){
if(answer==result)
System.out.println("passed! answer: "+answer+", result: "+result);
else
System.out.println("fail! answer: "+answer+", result: "+result);
}
public void test(List<List<Integer>> answer, List<List<Integer>> result){
if(answer.equals(result))
System.out.println("passed! answer: "+answer.toString()+", result: "+result.toString());
else
System.out.println("fail! answer: "+answer.toString()+", result: "+result.toString());
}
public static void main(String[] args){
Solution solution=new Solution();
solution.test(solution.rob(new int[]{1,2,3,1})
, 4);
solution.test(solution.rob(new int[]{2,7,9,3,1})
, 12);
solution.test(solution.rob(new int[]{1,2})
, 2);
solution.test(solution.rob(new int[]{1,3,1})
, 3);
solution.test(solution.rob(new int[]{2,3,2})
, 4);
solution.test(solution.rob(new int[]{1,7,9,4})
, 11);
solution.test(solution.rob(new int[]{4,1,2,7,5,3,1})
, 14);
solution.test(solution.rob(new int[]{8,9,9,4,10,5,6,9,7,9})
, 45);
}
}GPT가 찝어준 문제점은 크게 세가지로, 큰 값부터 접근하는 방식은 문제를 해결할 수 없다(즉, 방향 부터가 잘못되었다. 현재의 방식에서 겪고있는 문제를 해결한다고 해도 다른 테스트 케이스에서 막힐 것이다), is_available()을 이용한 방문 여부 판독이 비효율적이기에 중복 계산이 많다, visited[]배열을 이용한 방문 표기 시 초기화 부분에서 비효율적인 연산이 증가된다는 것이다.
이 문제는 최적 부분 구조의 동적 프로그래밍 방식을 사용해야한다고 한다. 제안한 코드는 아래와 같다.
class solution{
public int rob(int[] nums) {
int length = nums.length;
if (length == 1) return nums[0];
if (length == 2) return Math.max(nums[0], nums[1]);
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[length - 1];
}
}매우 간단하게 해결했음을 알 수 있다. 문제에서 사용한 dp[]는 i번째 집까지 고려했을 때의 최대금액을 의미한다. i번째 집을 안털면 dp[i]=dp[i-1]와 동일해지고, i번째 집을 털면 dp[i]=dp[i-2]+nums[i]로 한칸 건너뛰어 고려해준다. 그리고 최종적으로 dp[length-1]을 리턴하여 최댓값을 계산한다.
이전에도 접근해본 적 있는 방법인데, 나는 순서에 집중하지 않느라고 이 방법을 생각하지 못한 것 같다. 큰 값을 우선적으로 생각하기에 순서가 중요하지 않은 문제라고 생각했지만 순서를 오히려 고려하여 원소 별 탐색을 쌓아간다는 관점으로 접근하니 문제가 쉽게 해결되는 것을 볼 수 있었다. 이 문제를 최대한 해결해보려고 노력하며 나름대로 테스트 케이스를 조금씩 해결해갔지만 그렇기에 더 새로운 방식을 생각하지 못했던 것 같다. 최대한 이러한 접근 방법을 기억해두도록 하자.
