[10월 3주차] 알고리즘

1. 흙길 보수하기 - 실버 1

출처 - https://www.acmicpc.net/problem/1911

1911번: 흙길 보수하기

 

  Sol) 800ms

<hide/>
public class Practice3 {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); // 물 웅덩이의 개수
        int l = scan.nextInt(); // 널판지 길이
        int[][] arr = new int[n][2];

        for(int i = 0;i < n; ++i){
            int start = scan.nextInt();
            int end = scan.nextInt();
            arr[i] = new int[]{start, end};
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return Integer.compare(o1[1], o2[1]);
                }
                return Integer.compare(o1[0], o2[0]);
            }
        });
        int ans = 0;
        int idx = 0;    //현재 물웅덩이 위치
        for(int i = 0; i < n; ++i){ // 웅덩이 개수만큼만
            if(arr[i][0] > idx){        //
                idx = arr[i][0];        // 새로운 범위
            }
            if(arr[i][1] >= idx){
                while(arr[i][1] > idx){
                    idx += l;       // 하나 깔아주고  널판지 길이만큼 건너뛴다.
                    ++ans;
                }
            }
        }
        System.out.println(ans);
    }
}

• int[] 배열을 정렬하는 메서드를 오버라이드한다.
• Arrays.sort(배열, "new Comparator....") 까지만 작성해도 자동 완성으로 추천된다.
  • 그럼 1차로는 0열 기준, 다음으로는 1열 기준으로 정렬되도록 구현한다.
• 현재 지나는 인덱스를 뜻하는 idx를 변수로 만든다.
• arr[i][0]은 지금 살펴볼 웅덩이의 맨 왼쪽을 뜻한다.
  • arr[i][1]: 가장 오른쪽를 뜻한다.
• 한 웅덩이에 대해 현재 idx가 오른쪽 인덱스(arr[i][1])에 도달하지 않은 경우 while문을 돌린다.
  • while문으로 살펴보면서 널판지를 추가한다. idx를 널판지 길이만큼 더한다.