leetcode - LongestArithmeticSubsequence (등차수열)

가장 긴 등차수열의 길이를 구하는 문제이다. 처음에는 dfs 형태로 구현을 했는데, 이상하게도 특정 테스트 케이스에서만 무한루프가 돌아 문제점을 찾지 못한 채 멈췄었다. rnum의 최대길이는 1000이기 때문에, 내가 예상한 반복 회수는 최악일 때 500500번이였다. 이 정도는 0.1초도 되지 않을 텐데, 현재 rnum에 들어가 있는 특정 케이스에서만 무한루프가 도는 상태이다. 

 

dfs이긴 하지만 한 숫자를 선택하면 그 다음 인덱스부터 탐색을 진행하기 때문에, 따로 boolean 배열은 쓰지 않았다.

package leetcode;

public class LongestArithmeticSubsequence {
    static int answer = 0;
    static int[] rnum = new int[]{1,1,0,0,1,0,0,1,0,1,0,1,1,1,0,1,1,0,1,1,0,0,1,1,0,1,0,1,1,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,1,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,0,0,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0,1,1,1,1,1,0,1,1,0,0,0,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,1,0,0,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,0,1,0,0,1,0,1,1,1,1,0,1,1,0,0,0,0,1,0,1,0,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,1,1,0,0,1,1,0,0,1,0,1,1,1,1,0,1,1,1,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,1,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,1,0,1,0,0,0,1,1,1,1,1};
    public static void dfs(int count, int start, int pre_ind, int jmp) {
        if (count == rnum.length) {
            if (count > answer) answer = count;
        } else {
            if (count > answer) answer = count;
            for (int i = start; i < rnum.length; i++) {
                if (count == 0) {
                    dfs(count + 1, i + 1, i, -1);
                }
                else if (count == 1) {
                    dfs(count + 1, i + 1, i, rnum[i] - rnum[pre_ind]);
                }
                else if (rnum[i] - rnum[pre_ind] == jmp) {
                    dfs(count + 1, i + 1, i, jmp);
                }
            }
        }
    }

    public static int longestArithSeqLength() {
        answer = 0;
        dfs(0, 0, 0, 0);
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(longestArithSeqLength());
    }
}

 

고민을 계속하던 도중, dp 방식으로도 문제를 풀 수 있을 듯했다. 모든 수열 문제가 그렇듯이, A의 가장 끝 인덱스를 N이라고 하면

d[N] = d[N - 1]까지의 최대 등차수열 길이 + 1 이기 때문에, 비교적 간단한 점화식으로 풀 수 있을 듯했다.

한 숫자를 선택했을 때 그 숫자와 다른 숫자 간의 차를 이용해 탐색해야 하기 때문에, (같은 숫자를 고르더라도 이전 숫자가 무엇이냐에 따라서 다른 차를 가질 수 있다.) A의 길이만큼의 Hashmap을 이용해 구현했다.

 

    public static void main(String[] args) {
        int[] A = new int[]{1,1,0,0,1,0,0,1,0,1,0,1,1,1,0,1,1,0,1,1,0,0,1,1,0,1,0,1,1,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,1,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,0,0,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0,1,1,1,1,1,0,1,1,0,0,0,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,0,1,1,0,1,0,0,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,0,1,0,0,1,0,1,1,1,1,0,1,1,0,0,0,0,1,0,1,0,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,1,1,0,0,1,1,0,0,1,0,1,1,1,1,0,1,1,1,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,1,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,1,0,1,0,0,0,1,1,1,1,1};
        HashMap<Integer, Integer>[] map = new HashMap[A.length];
        int ans = 2;
        for (int i = 0; i < A.length; i++) {
            map[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                int d = A[i] - A[j];
                map[i].put(d, map[j].getOrDefault(d, 1) + 1);
                ans = Math.max(map[i].get(d), ans);
            }
        }
        System.out.println(ans);
    }

알고리즘은 간단하다. bottom up 방식이다.

숫자 하나를 선택한다.(A[i])

j를 0부터 i - 1까지 돌려, 각각의 등차를 구해 map[i] HashMap에 등차를 key로 하고, 길이를 value로 하는 값을 넣어준다.

이때, 넣을 때마다 최대 길이를 갱신해 후에 쓸 수 있도록 한다.

dp 방식으로는 쉽게 풀렸지만, 아직도 위의 dfs 코드가 왜 무한루프가 도는지는 모르겠다. 느려서 시간초과가 나는것은 그나마 이해라도 할 수 있지만, 왜 무한루프가..