프로그래머스(단속 카메라, 정수 삼각형) - Java

[단속 카메라]

https://programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라

 

* 조건

1. 각 차량별 고속도로 진입 구간과 진출 구간이 주어진다
2. 고속도로를 이용하는 모든 차량은 단속 카메라를 한 번은 만나야한다
3. 설치할 수 있는 최소의 카메라 수를 출력한다

* 알고리즘

• 최적의 상태가 있으면 계속 진행: 그리디 알고리즘

 

* 로직(Logic)

• 고속도로에서 벗어나는 시점을 기준으로 오름차순 정렬
• 제일 먼저 고속도로를 벗어나려는 차량부터 고려해야 한 번씩 카메라를 만나게 할 수 있다
• 카메라를 설치하는 구역(section) < 차량의 진입 구간이라면
  • 카메라를 설치하고
  • 카메라 설치 구역을 해당 차량의 진출 지점으로 갱신한다

 

import java.util.Arrays;
import java.util.Comparator;

public class Problem_CCTV {

    public static void main(String[] args) {
        int[][] routes = {
                {-20,15}, {-14,-5}, {-18,-13}, {-5,-3}
        };
        int answer = solution(routes);
        System.out.println(answer);
    }

    public static int solution(int[][] routes) {
        int answer = 0;

        //고속도로에서 나간 지점을 기준으로 오름차순 정렬
        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        // 자동차 진입 구간이 카메라 설치 구간을 벗어난다면 카메라 추가
        // 카메라 설치 구간을 해당 자동차가 벗어나는 지점으로 갱신
        int section = -30000;
        for(int[] route : routes){
            if(section <= route[0]){
                answer++;
                section = route[1];
            }
        }

        return answer;
    }
}

 

---

[정수 삼각형]

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

* 조건

1. 정수값이 입력된 삼각형이 주어진다
2. 삼각형 꼭대기에서 바닥까지 이어지면서 대각선으로 이동이 가능하다
3. 거쳐간 경로 중 최댓값을 출력한다

* 알고리즘

• DP

* 로직(Logic)

• dp[][] = 삼각형의 각 위치별 누적 값
• 삼각형의 양 끝변은 한 방향으로 가능하기 때문에 먼저 누적값들을 넣어준다
• 이후 양 끝변을 제외한 나머지 값들을 처리한다
  • 구하고자 하는 level의 위치를 기준으로, 바로 위의 level에 연결되어있는 2개의 누적 값 중 더 큰 값을 선택하고 더해준다
• 맨 마지막 level에 누적된 값들이 존재하게되고, 이 값들 중 최대 값을 출력한다

 

public class Problem_Triangle {

    public static void main(String[] args) {
        int[][] triangle = {
                {7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}
        };
        int answer = solution(triangle);
        System.out.println(answer);
    }

    public static int solution(int[][] triangle) {
        int answer = 0;
        //행: level, 열: 누적 값
        int[][] dp = new int[triangle.length][triangle.length];

        //삼각형 양쪽 변들의 누적을 넣어준다
        dp[0][0] = triangle[0][0];
        for(int i=1; i<triangle.length; ++i){
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
        }

        //양쪽 변들을 제외한 나머지 값들 처리
        for(int i=2; i<triangle.length; ++i){
            for(int j=1; j<i; ++j){
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }

        //마지막 level의 값들 중 최댓값 출력
        for(int i=0; i<dp[triangle.length-1].length; ++i){
            answer = Math.max(answer, dp[triangle.length-1][i]);
        }

        return answer;
    }
}