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

🤔 Intuition

첫 인상에서 그리디/Meeting-room-problem과 유사해보였습니다.

그리디로 선택을 한다고 할 때, 예외가 있는지 고민해봤는데

결국 널빤지를 최소한으로 깔아야 하니 최대한 길게 배치하는게 좋다는 건 자명하면서,

널빤지 영역을 빠짐없이 커버해야 하니까 결국 시작점을 기준으로 그리디하게 배치하면 문제 없겠다 싶었습니다.

 

다만, 하나의 널빤지로 두 웅덩이를 커버할 경우, 이를 체크할 수 있냐 없냐가 포인트였던 것 같고,

저는 이걸 마지막으로 널빤지를 두었던 좌표 +1 좌표(다음 널빤지를 놓기 시작할 위치) int lastIdx라는 변수로 저장하여 이를 기준으로 다음 웅덩이의 시작점 int s와 끝점 int e를 이용해 if 분기로 검사해 주었습니다.

이 과정에서 널빤지 개수가 좌표에 따라 딱 떨어지지 않는 경우가 더 많을테니 나누기와 나머지 연산을 적절히 활용하여 널빤지 개수를 계산하는 게 필요했습니다.

🔎 Algorithm & Complexity

• algorithm : greedy
• time complexity : O(N log N) - 물웅덩이 개수만큼 iteration O(N) + 물웅덩이 좌표들 sort O(N * log N)
• space complexity : O(N) - 물웅덩이 좌표를 저장 O(N)

🧑‍💻 Logic

1. 웅덩이 좌표들을 int[]으로 저장합니다. (이때 범위가 [start, end) 꼴임을 주의
2. 웅덩이 좌표를 iteration하면서 (s,e) 튜플을 '마지막으로 널빤지를 놓은 위치 lastIdx' 와 비교
3. 만약 lastIdx가 웅덩이 시작점보다 작거나 같으면 그대로 널빤지 깔면 됨
4. 만약 시작점보다는 크고, end 보다는 작으면 남은 길이만큼만 널빤지 깔면 됨
5. 그 외 경우에는 널빤지를 굳이 깔 필요 없으니 pass

public class BOJ_1911_흙길보수하기 {
    private static int N, L;
    private static int[][] arr;
    private static long ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        arr = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        // 그리디를 위한 정렬
        Arrays.sort(arr, Comparator.comparingLong(o -> o[0]));

        int lastIdx = 0; // 널빤지를 마지막으로 둔 위치
        for (int[] ptr : arr) {
            // 웅덩이 좌표 [s,e)
            int s = ptr[0];
            int e = ptr[1];

            // 다시 차곡차곡 쌓으면 되는 경우
            if (s >= lastIdx) {
                lastIdx = s;
                int length = e - s;
                int share = length / L;
                int remainder = length % L;
                ans += share + (remainder > 0 ? 1 : 0); // 널빤지 개수 추가
                lastIdx += (share + (remainder > 0 ? 1 : 0)) * L;
            } else if (lastIdx < e) { // 중간에 마무리가 된 상태에서 널빤지를 더 깔아야 하는 상황인 경우
                int length = e - lastIdx;
                int share = length / L;
                int remainder = length % L;
                ans += share + (remainder > 0 ? 1 : 0); // 널빤지 개수 추가
                lastIdx += (share + (remainder > 0 ? 1 : 0)) * L;
            }
        }
        sb.append(ans);
        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

🔥 Compare

친구의 로직은 조금 더 영리하게 구성되었다. (실행시간 : 224 ms)

 

친구 로직의 요지는 다음과 같다.

항상 널빤지를 깔게 되는 거니 이는 기본적으로 수행한다고 가정하고, "중간부터 널빤지를 까는 경우인지, 깔지 않아도 되는 경우인지"만 분기로 체크

 

다음 code snippet은 물 웅덩이 좌표 iteration 시 해당 로직을 구현한 부분이다.

for(int i=0;i<N;i++) {
    Water water=waters.get(i); // Water : 물 웅덩이 시작점과 길이를 담는 instance
    int start=water.start;
    int length=water.length;

    if(start<lastIdx) { // 중간부터 널빤지를 까는 경우
        length -= lastIdx - start; // 이미 널빤지가 깔린 만큼 길이를 줄여주고
        start = lastIdx; // 널빤지를 까는 시작 좌표 갱신

        if(length<=0) continue; // 널빤지를 깔 필요가 없는 경우엔 pass
    }

    int adder = (length % L == 0)? length / L : length / L + 1; // 개수 갱신

    lastIdx = start + L * adder; // 좌표 갱신
    result += adder;
}