프로그래머스LV2_11

피로도

접근 과정

1. 시작 지점에서 방문할 수 있는 순서를 모두 확인해야 하므로 dfs로 끝까지 탐색한다.
2. 방문 체크를 dfs 후에 해제하여 다음 시작 지점에서 다시 방문하는 경로를 체크할 수 있도록 해야 한다.(백트래킹)

시행착오

• 2중 for문으로 순서대로 가는 경우와 반대로 오는 경우를 생각했는데 길이가 4이면 1-3-2-4 같은 경우는 체크가 안되서 이전에 C++로 풀었던 풀이를 참고하였다.

해결 코드

• dfs와 백트래킹을 활용하여 방문한 곳을 체크해두고 dfs 끝난 후 체크를 해제하여 또 다시 방문할 수 있도록 하여 해결

class Solution {
    public int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        dfs(k, dungeons, 0, visited);
        return answer;
    }
    
    public void dfs(int k, int[][] dungeons, int cnt, boolean[] v){
        for(int i = 0; i < dungeons.length; i++){
            if(!v[i] && dungeons[i][0] <= k){
                v[i] = true;
                dfs(k - dungeons[i][1], dungeons, cnt + 1, v);
                v[i] = false;
            }
        }
        answer = Math.max(answer, cnt);
    }
}

시간 및 공간 복잡도

• 시간 복잡도(모든 순열을 검사해야 함)

• 공간 복잡도(visited 배열과 dfs 탐색으로 쌓이는 콜 스택)

행렬의 곱셈

접근 과정

1. 행렬의 곱셈의 결과는 첫 번째 행렬의 행의 개수와 두 번째 행렬의 열의 개수라는 것을 파악
2. 첫 번째 행렬은 행으로 고정하고 두 번째 행렬은 열로 고정하여 2 배열을 곱하여 더한 값을 answer[i][j]에 넣으면 해결

시행착오

• 행렬 곱셈이 헷갈려서 방식을 찾아서 해결했다.
• 너무 오랜만에 본 수학 공식이라 까먹었다…😢

해결 코드

• 행렬 곱셈 공식을 찾고 해결하였다.

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] answer = new int[arr1.length][arr2[0].length];
        for(int i = 0; i < arr1.length; i++){
            for(int j = 0; j < arr2[0].length; j++){
                int[] a1 = arr1[i];
                int[] a2 = new int[arr2.length];
                for(int k = 0; k < a2.length; k++){
                    a2[k] = arr2[k][j];
                }
                answer[i][j] = multi(a1, a2);
            }
        }
        return answer;
    }
    
    public int multi(int[] arr1, int[] arr2){
        int result = 0;
        for(int i = 0; i < arr1.length; i++){
            result += arr1[i] * arr2[i];
        }
        return result;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(arr1의 크기를 N M, arr2의 크기를 M K라고 할 때)

• 공간 복잡도

개선

• 중간에 2 배열을 곱하여 더하는 로직을 함수화 하지 않고 바로 anwer[i][j]에 넣는 것이 좀 더 간편하고 GC 관점에서 더 나아진다.

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] answer = new int[arr1.length][arr2[0].length];
        for(int i = 0; i < arr1.length; i++){
            for(int j = 0; j < arr2[0].length; j++){
                for(int k = 0; k < arr2.length; k++){
                    answer[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }
        return answer;
    }
}