[JAVA] [시간 초과] 프로그래머스 LEVEL4 경사로의 개수

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

프로그래머스

코딩테스트 연습 > 2023 현대모비스 알고리즘 경진대회 예선 > 경사로의 개수

 

문제 분석

난이도: LEVEL4

 

시간 초과 코드(30.4)

import java.util.*;
class Solution {
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static final int NUM = 1000 * 1000 * 1000 + 7;
    static int x_length, y_length;
    public int solution(int[][] grid, int[] d, int k) {
        x_length = grid.length; y_length = grid[0].length;
        int size = d.length * k;
        int [][] map = new int [grid.length][grid[0].length];
        
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                map[i][j] = grid[i][j];
                grid[i][j] = 1;
            }
        }
        
        for(int i = 0; i < k; i++){ // 10^9 
            for(int j = 0; j < d.length; j++){ // 10^2 
                
                int [][] copy = new int [grid.length][grid[0].length];
                
                for(int s = 0; s < grid.length; s++){ // 이전 시간 누적을 기록 
                    for(int t = 0; t < grid[0].length; t++){
                        copy[s][t] = grid[s][t];
                        grid[s][t] = 0;
                    }
                }
               
                for(int s = 0; s < grid.length; s++){  // 8
                    for(int t = 0; t < grid[0].length; t++){  // 8 
                        if(copy[s][t] == 0) continue;
                        int cur  = map[s][t];
                        int next = d[j]; // 다음 경사 
                        for(int z = 0; z < 4; z++){
                            int nx = s + arx[z];
                            int ny = t + ary[z];
                            if(validation(nx, ny)){
                                if(cur + next == map[nx][ny]){
                                    grid[nx][ny] += copy[s][t];
                                    grid[nx][ny] %= NUM;
                                }
                            }
                        }
                    }
                }
            }
        }
        int answer = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                answer += grid[i][j];
                answer %= NUM;
            }
        }
        return answer;
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < x_length && ny < y_length) return true;
        return false;
    }
}

결과

(8 / 24) 통과

나머지 시간초과 

 

설명 

시작 데이터 grid 격자의 모든 경우의 수를 1로 주고 시작 

격자의 모든 곳에서 이번 기울기에 맞게 움직일 수 있으면 이전 시간대의 경우의 수를 움직일 수 있는 곳에 + 해줌

 

그림 설명: 이번 경사가 1이고 이전 까지 경우의 수, 격자 상태가 그림과 같을 때 다음 경우의 수 결과  

 

이런 느낌으로 문제를 풀었는데 

 

경사로 반복의 변수 k가 1 <= k <= 10^9

 3 <= 격자(grid) 가로 크기 <= 8

 3 <= 격자(grid) 세로 크기 <= 8

경사로 배열의 크기 d가 1 <= d <= 100 

 

내 풀이 최악의 경우는 10^2 * 10^9 * 64 = 10^11 * 64 ...

 

시간 초과 코드2(30.4)

import java.util.*;
class Solution {
    static final int NUM = 1000 * 1000 * 1000 + 7;
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static int x_length, y_length;
    public int solution(int[][] grid, int[] d, int k) {
        x_length = grid.length; y_length = grid[0].length;
        
        // 0: sx, 1: sy 2: ex: 2: ey 좌표 저장 
        ArrayList<int[]>[] list = new ArrayList[201];
        for(int i = 0; i <= 200; i++){ // + 100씩 
            list[i] = new ArrayList<>();
        }
        
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < d.length; i++){
            set.add(d[i]);
        }
        
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()){
            int cur = it.next();
            for(int i = 0; i < grid.length; i++){
                for(int j = 0; j < grid[0].length; j++){
                    for(int t = 0; t < 4; t++){
                        int nx = arx[t] + i;
                        int ny = ary[t] + j;
                        if(validation(nx, ny)){
                            if(grid[i][j] + cur == grid[nx][ny]){
                                list[cur + 100].add(new int []{i,j,nx,ny});
                            }
                        }
                    }
                }
            }
        }
        int [][] memo = new int [grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++){
            Arrays.fill(memo[i], 1); // 시작 경우의 수 초기화 
        }
        
        for(int i = 0; i < k; i++){ 
            for(int j = 0; j < d.length; j++){
                int cur = d[j];
                int [][] copy = new int [grid.length][grid[0].length];
                for(int s = 0; s < grid.length; s++){
                    for(int t = 0; t < grid[0].length; t++){
                        copy[s][t] = memo[s][t];
                        memo[s][t] = 0;
                    }
                }
                for(int [] array : list[cur + 100] ){
                    memo[array[2]][array[3]] += copy[array[0]][array[1]];
                    memo[array[2]][array[3]] %= NUM;
                }
            }
        }
        int answer = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                answer += memo[i][j];
                answer %= NUM;
            }
        }
        return answer;
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < x_length && ny < y_length) return true;
        return false;
    }
}

 

1. 패턴을 미리 구한다. 

패턴?

경사로가 d인 경우 x1,y1 좌표 에서 x2,y2 좌표의 경우의 수를 더해라 

이런 패턴을 Deque에 기록하고 해당 경사로가 나올 때마다 사용 

2. 미리 구해둔 패턴을 바탕으로 경우의 수 계산 

3. 결과 반환 

 

... 결과 동일 

 

짜고 보니까 시간 복잡도가 동일하다 10^11 * 64  

for(int i = 0; i < k; i++){  // 10^9
    for(int j = 0; j < d.length; j++){ // 10^2 
        int cur = d[j];
        /*
        int [][] copy = new int [grid.length][grid[0].length];
        for(int s = 0; s < grid.length; s++){ // 8
            for(int t = 0; t < grid[0].length; t++){ // 8 
                copy[s][t] = memo[s][t];
                memo[s][t] = 0;
            }
        }
        for(int [] array : list[cur + 100] ){
            memo[array[2]][array[3]] += copy[array[0]][array[1]];
            memo[array[2]][array[3]] %= NUM;
        }
        */
    }
}

 

이렇게 주석 처리하고 돌리니까 시간 초과가 아닌 오답이 나온다. 

그럼 10^11 까진 허용이다!!

 

근데 내가 아는 지식으로는 어떻게 시간 복잡도를 더 줄일지 모르겠다.. 

10^9(k)번 돌리는 방법이 아닌 다른 수학적 방법으로 처리할 방법이 있을듯한데..