[프로그래머스] 도둑질 시간초과 해결 후기

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42897

 

---

1. 시간 초과 코드 (Java)

(1) 코드

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int N = money.length;
        int[][] dp = new int[N+1][2];

        for (int i=2; i<=N; i++) {
            dp[i][0] = Math.max(dp[i-2][0]+money[i-2], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-2][1]+money[i-1], dp[i-1][1]);
        }

        return Math.max(dp[N][0], dp[N][1]);
    }
}

 

(2) 채점 결과

대체 왜...?🥹🥹

 

처음에는 자바로 제출했는데, 시간복잡도가 O(N)인 코드를 제출했음에도 시간 초과를 받았다🤯

알고리즘의 문제인가? 싶어서 같은 코드를 C++로 만들어서 제출해봤다.

 

---

2. 통과 코드 (C++)

(1) 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    int answer = 0;
    int N = money.size();
    int dp[1000001][2] = {0, };
    
    for (int i=2; i<=N; i++) {
        dp[i][0] = max(dp[i-2][0]+money[i-2], dp[i-1][0]);
        dp[i][1] = max(dp[i-2][1]+money[i-1], dp[i-1][1]);
    }
    
    return max(dp[N][0], dp[N][1]);
}

 

(2) 채점 결과

🤔...❓

한번에 통과를 받았다. 이쯤 되면 알고리즘의 문제는 아니지 않나?😭

결국 자바로 해결할 수 있는 방법이 없는줄 알고 C++ 코드를 함께 제출했는데, 다른 스터디원은 자바로 통과를 받아왔다. 차이점을 찾아봤는데, 팀원분은 사이즈 N짜리 1차원 배열 2개를 썼고, 나는 N*2 크기의 2차원 배열을 썼다.

 

---

3. 통과 코드 (Java)

(1) 코드

class Solution {
    public int solution(int[] money) {
        int N = money.length;
        int[] first = new int[N+1];
        int[] last = new int[N+1];

        for (int i=2; i<=N; i++) {
            first[i] = Math.max(first[i-2]+money[i-2], first[i-1]);
            last[i] = Math.max(last[i-2]+money[i-1], last[i-1]);
        }

        return Math.max(first[N], last[N]);
    }
}

 

(2) 채점 결과

 

어마어마한 시간 차이로 통과를 받았다. 2차원 배열보다는 1차원 배열 2개의 접근 속도가 빠른 것 같다...🥲

 

 

이 밑으로는 풀이와 관련 없는 내용이지만 억울해서(...) 원인을 찾아보기로 했다. 

---

4. 자바에서 2차원 배열이 1차원 배열보다 느린 이유

 

출처: https://edoras.sdsu.edu/doc/javanotes7.0.1/c7/s5.html

사실 자바는 2차원 배열이 없다. 진짜 2차원 배열이면 모든 블럭들이 연속된 메모리 공간을 할당받아야 하지만, 자바는 그렇지 않다. 

자바에서 2차원 배열은 1차원 배열을 가리키는 포인터들의 집합이다. dp[1], dp[2] 등 각 행이 연속된 공간에 저장된다는 게 아니라는 의미. 아마 내가 dp 배열을 [N][2]로 선언해서 공간지역성의 이점을 많이 못본 것도 문제이지 않을까 싶다...🤔

 

---

5. 시간 측정 실험

import java.util.Stack;

class PGS_도둑질_Test {

    static final int N = 1_000_000;
    static final int M = 2;

    public static void main(String[] args) {

        int[][] dp = new int[N][M];
        int[] first = new int[N];
        int[] last = new int[N];

        for (int i=0; i<N; i++) {
            for (int j = 0; j < M; j++) {
                dp[i][j] = i * N + j;
            }
            first[i] = i;
            last[i] = i;
        }


        access1D(first, last);
        access2D(dp);
    }

    static void access1D(int[] first, int[] last) {
        long startTime = System.nanoTime();
        for (int i=0; i<N; i++) {
            int tmp = first[i];
            tmp = last[i];
        }
        long endTime = System.nanoTime();

        System.out.println("1D Execution Time: " + (endTime-startTime));
    }

    static void access2D(int[][] dp) {
        long startTime = System.nanoTime();
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                int tmp = dp[i][j];
            }
        }
        long endTime = System.nanoTime();
        
        System.out.println("2D Execution Time: " + (endTime-startTime));
    }
}

 

1D Execution Time: 3622167
2D Execution Time: 5276750

 

확실히 찍힌 시간을 보니 2차원 배열이 더 느렸다. 시간 제한이 빡빡한 문제에서 N*M 크기의 2차원 배열을 선언한다면, 더 작은 수를 앞으로 두는 게 좋을 것 같다.