[코테] 선인장 숨기기 (프로그래머스 Lv.2, C++)

최근 C++ 스터디를 시작했다.

'가랑비에 옷 젖듯이'라는 컨셉의 스터디이고,

문제 난이도에 따라서 일주일마다 팀원끼리 돌아가면서 1~3문제씩 가져오면 이를 같이 일주일 deadline으로 풀고 공유하는 스터디이다.

근데 이번에 한 팀원분이 엄청 어려운 문제를 가져오셨다. 난 Lv.1도 허덕이는데..

 

그래서 이번 문제는 푸는 거에 의의를 두지 않고 코드 해석하는 데에 의의를 두었다.

언젠가 이런 문제도 C++로 거뜬하게 풀 수 있길 바라면서 시작!

 

문제

선인장을 최대한 비 안 맞는 위치에 두는 문제이다.

문제 만드는 사람들 정말 창의적이다. 재밌는 문제 진짜 잘 만든다.

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

m개의 행과 n개의 열로 구성된 격자가 주어지며, 이는 사막 지도를 나타냅니다. 사막 지도의 가장 왼쪽 위칸 좌표는 (0, 0), 오른쪽 아래칸 좌표는 (m-1, n-1)입니다. 이 사막 어딘가에 가로 w, 세로 h 크기의 선인장 구역을 조성하려 합니다. 선인장 구역은 격자 축에 맞춘 연속된 w × h 크기의 부분 격자이며, 회전할 수 없습니다.
비구름은 미리 정해진 순서대로 격자의 여러 칸에 비를 뿌립니다. 이때 빗방울이 처음으로 선인장 구역에 포함된 칸에 떨어졌을 때, 그 시점을 선인장이 처음으로 비를 맞는 순간으로 기록합니다. 당신은 선인장이 가능한 한 늦게 비를 맞도록, 선인장 구역의 위치를 정하려고 합니다.

- 선인장이 비를 맞지 않도록 선인장 구역의 위치를 정할 수 있다면 해당 위치가 가장 우선됩니다.
- 가능한 늦게 비를 맞는 선인장 구역 후보가 여러 개라면 그중 가장 위쪽 행, 그래도 여러 개면 가장 왼쪽 열에 위치한 구역을 선택합니다.

격자의 세로 길이와 가로 길이를 나타내는 정수 m, n, 선인장 구역의 세로 길이와 가로 길이를 나타내는 정수 h, w, 그리고 빗방울이 떨어지는 순서대로 칸의 좌표를 담은 2차원 정수 배열 drops가 매개변수로 주어집니다. 주어진 조건을 만족하는 선인장 구역에 포함된 가장 왼쪽 위칸의 좌표를 정수 배열로 return 하도록 solution 함수를 완성해 주세요.

제한사항
1 ≤ m, n ≤ 500,000
1 ≤ m × n ≤ 500,000

(이하 생략)

직관적으로 보기 위한 입출력 예 1개 첨부합니다.

 

코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int m, int n, int h, int w, vector<vector<int>> drops) { //vector<vector<int>>: 2차원 배열
    int dropCount = drops.size();
    // 각 칸에 몇 번째 빗방울이 떨어지는지 저장. 비가 떨어지지 않는 칸은 dropCount + 1
    vector<vector<int>> dropTime(m, vector<int>(n, dropCount + 1)); // 2차원 벡터 만들기
    for (int i = 0; i < dropCount; i++) { // drops 내용을 dropTime에 옮기기
        int r = drops[i][0];
        int c = drops[i][1];
        dropTime[r][c] = i + 1; // 몇 번째 비가 떨어졌는지 기록
    }

    // 처음 k개의 빗방울을 피할 수 있는 h x w 영역이 존재하는지 확인하는 함수
    auto canAvoid = [&](int k, int &resultR, int &resultC) { // 임시 함수. //[&]: 바깥쪽 변수를 참조해서 사용
        // 2차원 누적합
        vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int rainy = 0;
                if (dropTime[r][c] <= k) { // (r,c)에 비가 떨어지는 순서가 k 이하인지 확인
                    rainy = 1;
                }
                prefix[r + 1][c + 1] = prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c] + rainy;
            }
        }

        // 가능한 모든 h x w 영역 확인. 위 -> 왼쪽 확인
        for (int r = 0; r <= m - h; r++) {
            for (int c = 0; c <= n - w; c++) {
                int bottom = r + h; // 아래쪽 경계값
                int right = c + w; // 오른쪽 경계값
                // 현재 h x w 영역 안에 처음 k개의 빗방울이 몇 개 들어있는지
                int count = prefix[bottom][right] - prefix[r][right] - prefix[bottom][c] + prefix[r][c];
                if (count == 0) { // 비 하나도 없을 때
                    resultR = r;
                    resultC = c;
                    return true;
                }
            }
        }
        return false; // 비 피하기 불가능하면 false
    }; // 람다는 마지막에 세미콜론 붙임

    // 이분 탐색. 최대 몇 개의 빗방울까지 피할 수 있는지 찾기. 입력이 최대 500,000개라서 이분탐색 써야 함
    int left = 0;
    int right = dropCount;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        int tempR = 0;
        int tempC = 0;
        if (canAvoid(mid, tempR, tempC)) {
            // mid개까지 피할 수 있음. 더 많이 피할 수 있는지 확인
            left = mid;
        }
        else {
            // mid개까지는 피할 수 없음
            right = mid - 1;
        }
    }

    // 위에서 찾은 최대한 오래 버틸 수 있는 경우 중 가장 위쪽 → 가장 왼쪽 위치 찾기
    int answerR = 0;
    int answerC = 0;
    canAvoid(left, answerR, answerC);
    return {answerR, answerC};
}

 

 

아유 해석만 하는데도 어렵다.

다들 같이 생초보인 스터디인데..다음에는 좀 쉬운 문제로 풀자고 해야겠다.