[프로그래머스/JAVA] Level 2, 땅따먹기

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

---

문제 요약

---

문제의 자세한 내용은 링크를 확인해 주세요.

(Nx4) 크기의 이차원 배열에서 마지막 행까지 모두 내려왔을 때 얻을 수 있는 점수의 최댓값 구하기
단, 같은 열을 연속해서 밟을 수 없습니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예시

 

문제 풀이

---

1. 첫 번째 풀이, 잘못된 접근 (실패) 

코드를 보려면 아래 [더 보기]를 눌러주세요.

int answer = Integer.MIN_VALUE;
    
int solution(int[][] land) {
    search(land, 0, new HashSet(), 0);
    return answer;
}

void search(int[][] land, int currRow, Set<Integer> visit, int total) {

    if(currRow == land.length) {
        answer = Math.max(answer, total);
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (visit.contains(i)) continue;
        total += land[currRow][i];
        visit.add(i);
        search(land, currRow+1, visit, total);
        total -= land[currRow][i];
        visit.remove(i);
    }
}

처음 문제를 읽었을 때 굉장히 단순하게 생각했습니다. DFS로 완전 탐색하면서 밟았던 행은 배열에 저장해 두고, 다시 밟지 않는 방법으로 풀이 아이디어를 생각했습니다. 따라서 행의 최대 개수가 100,000 개여도 한번 지난 행은 체크하지 않기 때문에 실행 속도에 문제가 있을 것이라고 생각하지 않았습니다.

결과는 실패입니다. 

1) 실패 이유

1. 먼저 문제를 잘못 이해했습니다. 제가 이해했던 방식은 한번 밟은 열을 다시 밟지 않는 것입니다. 따라서 Set에 한번 밟은 열을 저장했는데요. (생각을 깊게 해 보니,,) 열이 4개로 고정되었기 때문에, 제가 이해한 방식이라면, 행은 최대 4개였을 것입니다. 

2. 문제를 제대로 이해했다고 가정하고, DFS 풀이 시간복잡도를 계산해 보겠습니다. 
문제를 제대로 이해하고, 위와 같이 DFS 알고리즘으로 풀었다면, 시간복잡도는 O(4^N)입니다.
이유는 모든 행마다 4개의 선택지를 완전 탐색하기 때문입니다. 행이 100,000 개라면 4^100,000 이 되기 때문에 큰 시간이 발생합니다.

2) 문제를 제대로 이해했다고 가정, DFS 알고리즘 풀이 (잘못된 접근)

코드를 보려면 아래 [더 보기]를 눌러주세요.

int answer = Integer.MIN_VALUE;

int solution(int[][] land) {
    search(land, 0, -1, 0);
    return answer;
}

void search(int[][] land, int currRow, int pastColumn, int total) {

    if(currRow == land.length) {
        answer = Math.max(answer, total);
        return;
    }

    for (int i = 0; i < 4; i++) {
        if(i == pastColumn) continue;
        search(land, currRow+1, i, total+land[currRow][i]);
    }
}

 

2. 두 번째 풀이 (최적화)

코드를 최적화하기 위해선 DP(Dinamic Programming) - 동적 계획법으로 문제를 해결해야 합니다. 각 열에 max값을 저장하면서 풀어가는 방식입니다.

즉, 현재 위치한 값과 이전 행에서 현재 열과 일치하지 않은 열들 중 가장 큰 값을 더하면서 이차원 배열에 저장하는 방식입니다. 

예시

1) 행이 1 개일 경우 

해당 행에서 가장 큰 값을 구하면 됩니다.

2) 행이 2개일 경우

행이 2개일 경우입니다. a(1,0)을 밟는다고 가정했을 때, 최댓값을 구하려면 어떻게 해야 할까요? 0번째 열을 제외한 a(0,1), a(0,2), a(0,3) 중 가장 큰 값을 a(1,0)과 더하면 됩니다.

a(1,1)을 밟는다고 가정하면, 이전 행에서 1번 열을 제외한 값 중 가장 큰 값을 현재 밟은 땅과 더하면 됩니다.

그럼 두 번째 행에서 각 열을 밟을 때의 최댓값들이 나올 것입니다. 여기서 가장 큰 값이 우리가 찾으려는 최종 최댓값입니다.

3) 행이 3개일 경우 

위 예시의 값이 있다고 가정하겠습니다.

(1,0) 지점에 땅을 밟을 때 최댓값을 해당 칸에 저장합니다. 보다시피 같은 열에 있는 값을 제외하고, 나머지 값 중 최댓값과 현재 땅의 값을 더합니다.

(1,1) 지점도 동일하게 진행합니다. 이런 식으로 2번째 행(1번 인덱스)까지 땅을 밟을 때 최댓값을 각각 저장합니다.

2번째 행까지 갈 수 있는 최댓값들을 저장했으니 동일하게 이를 활용해서 마지막 행까지 값을 구합니다.

최종 문제 해결

최종으로는 제일 마지막 행에서 가장 큰 값인 16이 구하려던 최대 점수입니다.

---

풀이 일반화

문제를 재정의 하면, N번째 행까지 도달했을 때 가장 큰 값을 가진 열을 찾는 것입니다. 

그리고 N번째에 도달하기 위해선, N-1 행에서 같지 않은 열 중 가장 큰 값을 N 번째 값과 더하면 됩니다.

 

동적 계획법으로 문제를 잘 풀기 위해선 문제를 어떻게 쪼갤 것이냐가 중요합니다. 해당 문제는 '열이 같은지, 같지 않은지'를 기준으로 하위 문제로 나눌 수 있겠습니다.

또 중요한 점은 메모이제이션인 것 같습니다. 하위 문제로 이동했을 때 가장 큰 값들을 잘 저장해야 합니다.

사실 이 두 가지는 동적 계획법에 중요한 정의입니다. 해당 문제를 풀면서 다시 한번 생각할 수 있었습니다.

 

2. 동적 계획법 활용 코드

package letsdoIt.random;

import java.util.Arrays;

public class PG_12913_sol2 {

    // 배열 자체를 dp로 활용 -> 약간 누적합 느낌
    int solution(int[][] land) {

        int n = land.length; // 행의 개수

	// 이전 행에서 현재 밟은 땅의 열과 같지 않은 열중 가장 큰 수를 현재 땅의 값과 더함.
        // 더한 값을 현재 땅에 저장하면서 누적
        for (int i = 1; i < n; i++) {
            land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3]);
            land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3]);
            land[i][2] += max(land[i-1][0], land[i-1][1], land[i-1][3]);
            land[i][3] += max(land[i-1][0], land[i-1][1], land[i-1][2]);
        }

        return Arrays.stream(land[n-1]).max().getAsInt();
    }

    int max(int v1, int v2, int v3) {
		return Math.max(Math.max(v1,v2), v3);
    }
}

 

또 다른 풀이 [더 보기] 클릭

import java.util.Arrays;

/**
 * 이 문제는 동적 계획법으로 최적화해야함.
 * 각 행에서 4개의 열 중 1개를 선택하므로, 전체 경우의 수는 4^N이 아니라 N4 가 됨.
 * 따라서 시간 복잡도 O(N)
 */
public class PG_12913_sol {

    int solution(int[][] land) {

        // 행의 개수
        int n = land.length;
        int[][] dp = new int[n][4];

        // land 에서 첫 번째 행의 값은 그대로 dp에 저장
        for (int i = 0; i < 4; i++) {
            dp[0][i] = land[0][i];
        }

        // 두 번째 행부터는 이전 행에서 선택한 열과 겹치지 않는 열을 선택하여 최대값 구함
        for (int i = 1; i < n; i++) {
            // 현재 선택한 열
            for (int j = 0; j < 4; j++) {
                int max = 0;
                // 현재 선택한 행과 겹치지 않는 이전까지 행중 가장 큰 값 구하기
                for (int k = 0; k < 4; k++) {
                    if (j==k) continue;
                    max = Math.max(max, dp[i-1][k]);
                }
                // 현재 선택한 열의 값과 이전까지의 최대값 더하기
                dp[i][j] = max + land[i][j];
            }
        }

        return Arrays.stream(dp[n-1]).max().getAsInt();
    }
}

 

시간 복잡도

---

해당 문제는 사실 DFS로도 충분히 풀 수 있습니다. 문제를 이해하는 데는 어렵지 않습니다. 하지만 O(4^N)이라는 어마어마한 시간복잡도로 인해서 좋은 풀이 방법은 아닙니다.

코드 최적화를 위해서 DP를 활용할 수 있는데요. 그러면 시간복잡도는 O(N)입니다. 그 이유는 코드를 봤을 때 한 번의 for문을 사용하기 때문에 알 수도 있습니다. 자세하게는 각 행마다 선택 가능한 열의 최댓값을 저장하고, 다음 행에서 이전까지 저장한 내용을 선택해서 사용합니다.

이때, 각 행에서 선택 가능한 열은 최대 4개이므로, 각 행에서의 계산 시간은 상수입니다. 따라서 N개의 행에 대해서 한 번씩만 계산하므로, 전체 시간복잡도는 O(N)이 됩니다.