[백준] Java 1911 흙길 보수하기

문제

https://www.acmicpc.net/problem/1911

알고리즘

정렬
스위핑 알고리즘

풀이

스위핑 알고리즘

처음 길이부터 끝까지 한번만 스캔하면서 문제를 해결하는 것.

일단 스위핑 알고리즘을 이용하려면 배열을 정렬시켜야 한다.
1. 웅덩이 시작점 오름차순
2. 시작점이 같으면 끝점으로 오름차순

위처럼 정렬을 한 다음에 스위핑 알고리즘을 이용하여 처음부터 스캔을 한다.
1. for문으로 웅덩이를 순회하면서 range로 선언한 변수가 웅덩이 시작점보다 작으면 range를 갱신해준다.
2. 웅덩이 끝점이 range보다 크면 널빤지를 깔아준다.
3. 웅덩이 끝점이 range보다 큰 경우에 널빤지를 깔고 range를 널빤지 길이만큼 증가시켜준다.
4. while문이 돌때마다 널빤지 개수인 answer를 +1 해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    public int solution(int[][] n, int m) {

        int answer = 0;
        int range = 0;

		// 웅덩이를 정렬시켜준다.
        Arrays.sort(n, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            } else {
                return o1[0] - o2[0];
            }
        });

		// 웅덩이를 순회하면서 널빤지를 깔아준다.
        for (int[] ints : n) {
            if (ints[0] > range) {
                range = ints[0];
            }

            if (ints[1] > range) {
                while (ints[1] > range) {
                    range += m;
                    answer++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {

        Main solution = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] nn = new int[n][2];
        for (int i = 0; i < n; i++) {
            int[] nnn = new int[2];
            StringTokenizer stt = new StringTokenizer(br.readLine());
            nnn[0] = Integer.parseInt(stt.nextToken());
            nnn[1] = Integer.parseInt(stt.nextToken());
            nn[i] = nnn;
        }

        System.out.println(solution.solution(nn, m));

        br.close();
    }
}