Programmers Lv3, 징검다리 건너기[C++, Java]

junto·2024년 7월 5일

programmers

목록 보기

43/66

문제

[Programmers Lv3, 단속카메라](https://school.programmers.co.kr/learn/courses/30/lessons/42884)

핵심

입력의 크기가 200,000,000과 200,000이다. 200,000을 기준으로 대략 $O(N * logN)$ 이하 알고리즘을 사용한다.

1. 단순한 접근

단순하게 구현하면, 한 명씩 건너면서 건널 때마다 돌다리값을 -1로 줄일 수 있다. 돌다리값은 200,000,000이기 때문에 200,000 * 200,000,000이란 말도 안 되는 시간복잡도가 나온다. 처음 시도해 본 코드는 아래와 같다.

bool cross_stones(vector<int>& stones, int k) {
    int size = stones.size();
    int cur_stone = -1;
    int nxt_stone = -1;
    int ans = 0;
    while (true) {
        ++cur_stone;
        if (cur_stone == size)
            return true;
        nxt_stone = cur_stone;
        while (stones[nxt_stone] <= 0) {
            ++nxt_stone;
            if (nxt_stone == size) {
                if (nxt_stone - cur_stone >= k) {
                    return false;
                }
                return true;
            }
        }
        if (nxt_stone - cur_stone >= k)
            return false;
        cur_stone = nxt_stone;
        stones[cur_stone] -= 1;
    }
}

int solution(vector<int> stones, int k) {
    
    int ans = 0;
    while (true) {
        if (!cross_stones(stones, k)) {
            break;
        }
        ++ans;
    }
           
    return ans;
}

구현이 복잡한데 아래와 같이 돌다리값에 따라 연속적으로 건널 수 있는 개수를 구하면 간단명료하게 코드를 작성할 수 있다.

bool cross_stones(vector<int>& stones, int k) {
    int step = 0;
    for (auto& e : stones) {
        if (e <= 0) {
            ++step;
            if (step >= k) {
                return false;
            }
        } else {
            step = 0;
            e -= 1;
        }
    }
    return true;
}

2. 이진 탐색

생각해 보면, 돌의 값은 건널 수 있는 사람의 수를 의미한다. 다리를 한 번에 건널 수 있는 인원을 최댓값으로 하여 건널 수 있는 인원을 이진 탐색으로 탐색하는 방법을 시도해 볼 수 있다.
일반적으로 이진 탐색을 하기 전에 정렬하는데, 해당 문제에서는 필요 없다. 그 이유는 건널 수 있는 최대 사람 수를 찾는 함수(cross_stones)가 존재하며 해당 함수 반환 조건에 따라 left, right가 조정되어 원하는 값으로 수렴하기 때문이다. 일반적인 이진 탐색에서 특정한 요소를 찾는 작업이 아니다.

1. C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool cross_stones(vector<int>& stones, int k, int people) {
    int step = 0;
    for (auto& e : stones) {
        if (e < people) {
            ++step;
            if (step >= k) {
                return false;
            }
        } else {
            step = 0;
        }
    }
    return true;
}

int solution(vector<int> stones, int k) {
    
    int ans = 0;
    int st = 0;
    int en = *max_element(stones.begin(), stones.end()); 
    while (st <= en) {
        int people = (st + en) / 2; 
        if (cross_stones(stones, k, people)) {
            st = people + 1;
            ans = max(ans, people);
        } else {
            en = people - 1;
        }
    }
           
    return ans;
}

2. Java

import java.util.*;

public class Solution {

    boolean crossStones(int[] stones, int k, int people) {
        int step = 0;
        for (var e : stones) {
            if (e < people) {
                ++step;
                if (step >= k) {
                    return false;
                }
            } else {
                step = 0;
            }
        }
        return true;
    }

    public int solution(int[] stones, int k) {
        int ans = 0;
        int st = 0;
        int en = Arrays.stream(stones).max().getAsInt();

        while (st <= en) {
            int people = (st + en) / 2;
            if (crossStones(stones, k, people)) {
                st = people + 1;
                ans = Math.max(ans, people);
            } else {
                en = people - 1;
            }
        }

        return ans;
    }
}

3. 슬라이딩 윈도우

슬라이딩 윈도우를 이용하면 더욱 간단하게 풀 수 있다. 하지만, 이해하는 과정은 간단하지 않다. 두 가지 큰 흐름을 이해해야 한다.

(1) 최대 범위 K가 주어졌을 때 구간 K에서 최댓값은 건널 수 있는 사람의 최댓값이다.

입력 예제 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]

cursor가 다리의 시작 부분이라고 계산해도 되지만, 여기선 cursor가 다리의 끝부분이라고 생각하고 계산한다. 즉, index = 0에서 다리를 건널 수 있는 최대 인원은 2명이다. 하지만 index = 0에서 다리를 건널 수 있는 최대 인원은 2명이지만 구간을 포함하는 정상적인 돌다리는 아니기 때문에 제외해야 한다.
cursor가 index 2(5)에 있을 때는 최댓값이 5가 된다. cursor가 5의 범위 밖인 index 5에 있을 때 어떻게 최댓값을 효율적으로 구할 수 있을까?
- deque 자료 구조를 이용하면 O(1)에 알 수 있다.
- 최댓값은 deque의 앞에서 넣어 바로 조회할 수 있도록 하고, 최댓값이 아니지만 이후 구간에서 최댓값 후보라면 현재 최댓값이 유효 범위를 넘었을 때 바로 최댓값을 알 수 있도록 deque의 뒤에서 넣는다.
- 즉, 인덱스 3(5)에서 3이 이후 최대값 후보에 deque 뒤에 들어가고, 5가 범위 밖에 지나갔을 때 이를 앞에서 빼게 되면 자연스럽게 3이 구간의 최댓값으로 자리 잡는다.

(2) 구간 K에 건널 수 있는 사람의 수 중 가장 작은 값이 정답이다.

징검다리 초입에서 3명이 건널 수 있었다고 할 때, 뒤에서 10명이 건널 수 있어도 최대로 건널 수 있는 인원은 3명이 된다.

1. C++

#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> stones, int k) {

    deque<int> dq;
    vector<int> ans;

    for (int i = 0; i < stones.size(); ++i) {
 
        while (!dq.empty() && stones[dq.back()] <= stones[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        if (dq.front() <= i - k) {
            dq.pop_front();
        }

        if (i >= k - 1) { 
            ans.push_back(stones[dq.front()]);
        }
    }

    return *min_element(ans.begin(), ans.end());
}

2. Java

import java.util.*;

class Solution {

    public int solution(int[] stones, int k) {
        Deque<Integer> dq = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i < stones.length; ++i) {
            while (!dq.isEmpty() && stones[dq.getLast()] <= stones[i]) {
                dq.removeLast();
            }
            dq.addLast(i);

            if (dq.getFirst() <= i - k) {
                dq.removeFirst();
            }

            if (i >= k - 1) {
                ans.add(stones[dq.getFirst()]);
            }
        }

        return Collections.min(ans);
    }
}