[프로그래머스] 1833 캠핑 (C/C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1833

풀이

솔직히 못 풀었다. 블로그 포스트를 작성하지 말까 싶었지만, 개인 공부용이니 그래도 남겨본다.

첫 번째 시도

첫 시도에서는 $x + y = C$ 형태의 직선을 생각했다.

$C$ 의 값을 1씩 늘려가며 서로 평행한 직선을 만들고, 각 직선 위에 존재하는 쐐기들의 조합을 이용해 설치 가능한 텐트의 개수를 계산하려 했다.

한 직선 위의 점과 바로 다음 직선이 아닌 다다음 직선 위의 점으로 텐트를 만들면, 그 사이에 다른 쐐기가 존재할 가능성이 높다고 생각했다. 처음에는 나름 그럴싸한 접근이라고 생각했지만, 아래와 같은 반례를 쉽게 찾을 수 있었다.

text

(0, 1)과 (1, 0)은 각각

0 + 1 = 1

1 + 0 = 1

이므로 $C = 1$ 인 같은 직선 위에 있다.

같은 원리로 (3, 3)은 $C = 6$ 인 직선 위에 있고, (2, 5)와 (5, 2)는 $C = 7$ 인 직선 위에 있다. 이 접근에서는 (0, 1)과 (2, 5) 사이에 여러 직선이 존재하므로 해당 조합을 고려하지 않게 된다. 하지만 두 점이 만드는 직사각형 내부에 다른 쐐기가 없다면 실제로는 텐트를 설치할 수 있다.

결국 $x + y$ 값만으로는 두 점이 만드는 직사각형 내부에 다른 점이 있는지를 판단할 수 없었다.

두 번째 시도

다음 시도로 모든 점을 C++ STL 레드-블랙 트리 기반 컨테이너에 넣어 정렬된 상태로 만들었다.

이후 모든 두 점의 조합에 대해, 두 점이 만드는 직사각형 내부에 다른 쐐기가 존재하는지 확인하는 완전 탐색을 시도했다. lower_bound를 사용해 탐색을 시작할 위치를 찾았으므로 처음에는 어느 정도 시간 복잡도를 줄일 수 있을 것이라 생각했다.

lower_bound 자체는 $O(\log N)$ 이지만, 시작 위치를 찾은 뒤에는 조건에 맞는 점이 있는지 범위 안의 점들을 순차적으로 확인해야 했다. 내부에 있는 쐐기가 탐색 범위의 끝부분에서 발견되거나 아예 존재하지 않는 경우에는 최대 $O(N)$ 개의 점을 확인하게 된다.

두 점을 선택하는 경우의 수가 $O(N^2)$ 개이므로, 전체 최악 시간 복잡도는 $O(N^3)$ 이 되어 시간 초과가 발생했다.

좌표 압축과 2차원 누적합

이후 좌표 압축이라는 힌트를 보고 남은 로직을 생각해봤지만, 여전히 해답이 나오지 않았다. 추가로 2차원 누적합이라는 힌트까지 봤음에도 바로 풀이를 떠올리지 못했다.

누적합을 사용한다면 무엇을 누적해야 하는지, 단순히 쐐기의 개수를 누적하는 것만으로 텐트 설치 가능 여부를 확정할 수 있는지가 잘 연결되지 않았다. 심지어 자연어로 작성된 풀이를 본 이후에도 코드를 구현하는 과정이 쉽지는 않았다.

풀이는 먼저 쐐기들의 좌표를 압축해, 실제 좌표값 대신 서로의 상대적인 순서만 남기는 방식으로 시작한다. 좌표의 값 자체는 매우 크지만 쐐기의 개수는 한정되어 있으므로, 좌표 압축을 통해 쐐기들이 놓인 위치를 작은 격자 안에 표현할 수 있다.

이후 각 칸에 쐐기가 존재하는지 표시하고, 격자 전체에 2차원 누적합을 만든다. 그러면 임의의 두 쐐기를 선택했을 때, 두 쐐기가 만드는 직사각형 내부에 다른 쐐기가 몇 개 있는지를 빠르게 확인할 수 있다.

결국 모든 쐐기 쌍을 하나씩 확인하면서, 같은 행이나 같은 열에 있는 경우는 제외하고, 두 쐐기 사이의 직사각형 내부에 다른 쐐기가 하나도 없는 경우만 정답에 포함한다.

좌표 압축은 이번에 처음 알게 된 개념이다.

하지만 누적합을 처음 만났던 순간도 있었고, 2차원 누적합을 처음 만났던 순간도 분명 과거에 존재했다. 두 개념은 이미 알고 있던 개념인데도 이번 문제에서는 풀이로 연결하지 못했다.

역시 많이 맞아가며 경험으로 부딪히고 익숙해지는 수밖에 없는 것인가 싶다 ㅋㅋ,,

소스 코드

C++17

#include <bits/stdc++.h>

std::vector<std::vector<int>> create_compressed_grid(
    const std::vector<std::vector<int>> &coordinates
) {
    std::map<int, int> r_rank;
    std::map<int, int> c_rank;

    for (const auto &point: coordinates) {
        r_rank[point[0]] = 0;
        c_rank[point[1]] = 0;
    }

    int index = 0;
    for (auto &[ coordinate, rank ]: r_rank) {
        rank = index++;
    }

    index = 0;
    for (auto &[ coordinate, rank ]: c_rank) {
        rank = index++;
    }

    const int N = r_rank.size();
    const int M = c_rank.size();

    std::vector<std::vector<int>> ret(N, std::vector<int>(M));

    for (const auto &point: coordinates) {
        const int r = r_rank[point[0]];
        const int c = c_rank[point[1]];

        ret[r][c] = 1;
    }

    return ret;
}

std::vector<std::vector<int>> create_prefix_sum_grid(
    const std::vector<std::vector<int>> &grid
) {
    const int r_count = grid.size();
    const int c_count = grid[0].size();

    std::vector<std::vector<int>> prefix_sum_grid = grid;

    for (int r = 0; r < r_count; ++r) {
        for (int c = 0; c < c_count; ++c) {
            prefix_sum_grid[r][c] +=
                (0 < r ? prefix_sum_grid[r - 1][c] : 0) +
                (0 < c ? prefix_sum_grid[r][c - 1] : 0) -
                (0 < r && 0 < c ? prefix_sum_grid[r - 1][c - 1] : 0);
        }
    }

    return prefix_sum_grid;
}

std::vector<std::pair<int, int>> collect_planted_points(
    const std::vector<std::vector<int>> &grid
) {
    const int r_count = grid.size();
    const int c_count = grid[0].size();

    std::vector<std::pair<int, int>> planted_points;

    for (int r = 0; r < r_count; ++r) {
        for (int c = 0; c < c_count; ++c) {
            if (grid[r][c] != 0) {
                planted_points.push_back({ r, c });
            }
        }
    }

    return planted_points;
}

int solution(int n, std::vector<std::vector<int>> data) {
    const auto compressed_grid = create_compressed_grid(data);
    const auto prefix_sum_grid = create_prefix_sum_grid(compressed_grid);
    const auto planted_points = collect_planted_points(compressed_grid);

    const std::size_t planted_point_count = planted_points.size();

    int answer = 0;

    for (std::size_t i = 0; i + 1 < planted_point_count; ++i) {
        for (std::size_t j = i + 1; j < planted_point_count; ++j) {
            const auto [ r1, c1 ] = planted_points[i];
            const auto [ r2, c2 ] = planted_points[j];

            const int min_r = std::min(r1, r2) + 1;
            const int max_r = std::max(r1, r2) - 1;
            const int min_c = std::min(c1, c2) + 1;
            const int max_c = std::max(c1, c2) - 1;

            answer += (
                r1 != r2 && c1 != c2
            ) && (
                prefix_sum_grid[max_r][max_c] -
                prefix_sum_grid[max_r][min_c - 1] -
                prefix_sum_grid[min_r - 1][max_c] +
                prefix_sum_grid[min_r - 1][min_c - 1]
            ) == 0;
        }
    }

    return answer;
}

[프로그래머스] 1833 캠핑 (C/C++)

문제

풀이

첫 번째 시도

두 번째 시도

좌표 압축과 2차원 누적합

소스 코드

Share this post