treecode

게임 맵이 주어지면 목적지까지 가는 최단거리를 구하는 문제로 예전에 풀었던건데 오래 되기도 했고 연습할겸 다시 풀어보았다.

맵의 값이 1이면 이동 가능하고 최단거리를 구해야 하기 때문에 DFS로 풀면 시간 초과가 뜬다. (엉뚱한 길로 가도 끝까지 파고 들어가기 때문)

4방향으로 한칸씩 이동 가능한 단위 방향 배열을 만들고 이동 가능한 경우를 Queue에 넣어가면서 목적지에 도착하면 최단 거리를 구할 수 있다.

4방향이면 뒤로도 갈 수 있기 때문에 이동 경로를 체크하는 boolean 배열을 만들어준다.

예전에 풀었던 코드

while (!q.isEmpty()) {
    int len = q.size();
    for (int i = 0; i < len; i++) {
        Pos pos = q.poll();
        if (pos.y == y_length && pos.x == x_length) {
            answer = Math.min(answer, pos.move);
        } else {
            // 이동 가능하고 체크가 안된 경우
            if (graph[pos.y][pos.x] == 1 && ch[pos.y][pos.x] == 0) {
                // 이동 체크
                ch[pos.y][pos.x] = 1;
                // 일단 4방향 전부 Queue 삽입하고 poll에서 거름
                if (pos.y < y_length) q.offer(new Pos(pos.y + 1, pos.x, pos.move + 1));
                if (pos.y > 1) q.offer(new Pos(pos.y - 1, pos.x, pos.move + 1));
                if (pos.x < x_length) q.offer(new Pos(pos.y, pos.x + 1, pos.move + 1));
                if (pos.x > 1) q.offer(new Pos(pos.y, pos.x - 1, pos.move + 1));
            }
        }
    }
}

다시 보고 느끼는 이전 코드 문제점

- 최단거리를 찾고 멈추지 않음

- queue의 size()만큼 for문을 돌릴 이유가 없음 (Pos에 거리 move를 저장하고 있기 때문)

- if문으로 안되는 경로 컷트하고 되는 경로만 넣으면 되는데 일단 다 넣고 있음

// ...
	while (!players.isEmpty()) {
            Player player = players.poll();
            if (isClear(player)) {
                return player.distance;
            }
            
            // 방향 배열 dy,dx
            for (int i = 0; i < 4; i++) {
                int my = player.y + dy[i];
                int mx = player.x + dx[i];

                if (canMove(my, mx)) {
                    moved[my][mx] = true;
                    players.offer(new Player(my, mx, player.distance + 1));
                }
            }
        }
        return -1;
    }

private boolean isClear(Player player) {
    return (player.y == maps.length - 1 && player.x == maps[0].length - 1);
}

private boolean canMove(int my, int mx) {
    if (mx < 0 || mx == maps[0].length ||
            my < 0 || my == maps.length) {
        return false;
    }
    
    if (maps[my][mx] == 0 || moved[my][mx]) {
        return false;
    }
    
    return true;
}

강도가 집을 터는데 연속된 집을 털 수 없고 집마다 털 수 있는 금액이 nums[]로 주어질 때 가장 큰 값을 구하는 문제로 처음에는 재귀로 풀었는데 시간 초과가 떴다.

public void DFS(int i, int sum, int[] nums) {
	if (i >= nums.length) {
		answer = Math.max(answer, sum);
		return;
	}
    
    // 현재 집을 털 경우 sum에 더하고 연속된 집 건너뛰기 (i + 2)
    DFS(i + 2, sum + nums[i], nums);
    // 현재 집을 털지 않을 경우 sum에 더하지 않고 다음 집으로(i + 1)
    DFS(i + 1, sum, nums);
}

그래서 이전 집까지 털었을때의 최대값을 기록해두고 이를 이용하는 메모이제이션 방법으로 풀었다.

3번째 집까지 털었을때 최대값 - 2번째 집까지 털었을 때 최대값 vs 1번째 집까지 털었을 때 최대값 + 3번째 집을 털었을 때 값

4번째 집까지 털었을때 최대값 - 3번째 집까지 털었을 때 최대값 vs 2번째 집까지 털었을 때 최대값 + 4번째 집을 털었을 때 값

5번째 집까지 털었을때 최대값 - 4번째 집까지 털었을 때 최대값 vs 3번째 집까지 털었을 때 최대값 + 5번째 집을 털었을 때 값

...

    public int rob(int[] nums) {        
        int[] memo = new int[nums.length + 1];
        
        if (nums.length < 3) {
            return Arrays.stream(nums).max().getAsInt();
        }
        
        memo[1] = nums[0];
        memo[2] = Math.max(nums[0], nums[1]);
        
        for (int i = 3; i <= nums.length; i++) {
            memo[i] = Math.max(memo[i - 1], memo[i - 2] + nums[i - 1]);
        }
        
        return Arrays.stream(memo).max().getAsInt();
    }

행렬을 더하면서 내려갔을때 나오는 최소값을 구하는 문제로 x축으로는 -1, 0, 1만큼 이동할 수 있다.

끝 값이 어떻게 바뀔지 모르기 때문에 전부 확인해야 된다고 생각해서 방향 배열을 만들고 queue에다 계속 값을 더해가면서 전부 탐색을 했는데 역시 시간 초과가 발생했다.

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        Queue<Point> queue = new LinkedList<>();
        int min = Integer.MAX_VALUE;
        int n = matrix.length;
        int[] dx = new int[]{-1, 0, 1};

        for (int i = 0; i < n; i++) {
            queue.offer(new Point(0, i, matrix[0][i]));
        }

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int j = 0; j < 3; j++) {
                int mx = point.x + dx[j];
                int my = point.y + 1;
                if (my >= n) {
                    min = Math.min(min, point.sum);
                    continue;
                }
                if (mx < 0 || mx >= n) {
                    continue;
                }
                queue.offer(new Point(my, mx, point.sum + matrix[my][mx]));
            }
        }
        return min;
    }

    public static class Point {
        int y;
        int x;
        int sum;

        public Point(int y, int x, int sum) {
            this.y = y;
            this.x = x;
            this.sum = sum;
        }
    }
}

다른 풀이 코드를 확인해보니 이전 행에서 될 수 있는 최소값을 비교해가면서 구하는 식으로 깔끔하게 구현을 했다. 해당 자리에 올 수 있는 방법은 이전 행의 x축 [-1, 0, 1] 3가지 경우이기 때문에 3가지만 비교하면 된다. 인덱스 바운스를 Math.max(0, x - 1), Math.min(end, x + 1)로 처리할 생각은 못 해봤는데 하나 배웠다.

public int minFallingPathSum(int[][] matrix) {
    // n x n matrix
    int n = matrix.length;

    for (int y = 1; y < n; y++) {
        for (int x = 0; x < n; x++) {
            int middle = matrix[y - 1][x];
            int sideMin = Math.min(
                matrix[y - 1][Math.max(0, x - 1)], 
                matrix[y - 1][Math.min(n - 1, x + 1)]
            );

            matrix[y][x] += Math.min(middle, sideMin);
        }
    }

    return Arrays.stream(matrix[n - 1]).min().getAsInt();
}

날마다 주식 종가가 담긴 prices가 주어지는데 언제 매수해서 매도하는 것이 가장 큰 수익이 나는지 구하는 문제다.

for-each문으로 prices를 돌면서 작은 값이 나오면 min에 저장하고 price와 현재까지 최소 가격인 min의 차이로 최대 수익을 구한다.

현재 가격 price에서 최소 가격인 min을 뺀 수익을 계속 비교하기 때문에 최대 수익은 기록이 되고,

최소 가격이 갱신이 되더라도 남은 price와의 차이가 적으면 수익은 갱신이 되지 않는다.

public int maxProfit(int[] prices) {
    int min = Integer.MAX_VALUE;
    int profit = 0;

    for (int price : prices) {
        if (price < min) {
            min = price;
        }

        profit = Math.max(profit, price - min);
    }

    return profit;
}