[프로그래머스] Lv3 문제풀이3(feat. JAVA)

등굣길 - Dynamic Programming

class Solution {
    
    public long[][] dp;
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;

        dp = new long[n+1][m+1];
        dp[1][1] = 1;

        for(int[] a : puddles)
            dp[a[1]][a[0]] = -1;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(i == 1 && j == 1) continue;
                if(dp[i][j] == -1) continue;

                if(dp[i][j-1] == -1 && dp[i-1][j] == -1) {
                    dp[i][j] = -1;
                } else if(dp[i][j-1] == -1) {
                    dp[i][j] = dp[i-1][j];
                } else if(dp[i-1][j] == -1) {
                    dp[i][j] = dp[i][j-1];
                } else {
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1_000_000_007;
                }
            }
        }
        answer = Math.toIntExact(dp[n][m]);

        return answer;
    }
}

 

 

 

숫자게임

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;

        Arrays.sort(A);
        Arrays.sort(B);

        int j = 0;
        for(int i = 0; i < B.length; i++) {
            if(B[i] > A[j]) {
                j++;
                answer++;
            }
        }

        return answer;
    }
}

 

 

 

단속카메라 - Greedy Algorithm

import java.util.*;

class Solution {
    class Point {
        int start;
        int end;
        Point(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public int solution(int[][] routes) {
        int answer = 0;
        Queue<Point> cam = new LinkedList<>();

        ArrayList<Point> routeList = new ArrayList<>();
        for(int[] route : routes) {
            int start = route[0];
            int end = route[1];
            routeList.add(new Point(start, end));
        }

        routeList.sort((o1, o2) -> o1.end - o2.end);

        ArrayList<Point> result = new ArrayList<>();
        int last = -30_001;
        for(int i = 0; i < routeList.size(); i++) {
            if(routeList.get(i).start > last) {
                last = routeList.get(i).end;
                result.add(routeList.get(i));
            }
        }
        answer = result.size();
        return answer;
    }
}