[C++] Programmers 징검다리 건너기 (2019 카카오 개발자 겨울 인턴)

https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

징검다리는 숫자가 적혀있는 디딤돌로 구성되어있고, 사람이 디딤돌을 지나가면 적힌 숫자가 줄어든다고 할 때 징검다리를 건널 수 있는 최대 인원을 구하는 문제이다. 사람이 건널 때 징검다리에 있는 디딤돌을 딛고 건너야하되, 숫자가 0이 된 디딤돌이 있으면 점프를 해서 가야한다. 점프로 넘을 수 있는 디딤돌 개수 또한 주어진다.

풀이

(시도 1)

효율성을 보는 문제라서 안될 것은 알았지만 누구나 생각할 수 있는 naive한 접근 방식을 도전해보았다. 징검다리 길이 x 징검다리에 있는 숫자 중 가장 큰 수 크기의 2차원 벡터를 생성한다. 제한사항에는 건너는 사람이 무한하다고 주어져있지만, 실제로 디딤돌은 사람이 건널수록 숫자가 작아지며 결국 소멸하기 때문에 징검다리를 구성하는 디딤돌의 숫자 중 가장 큰 숫자만큼 최대로 건널 수 있다. 루프를 돌며 n명 건넜을 때 연속적으로 없어진 디딤돌이 주어진 점프 가능한 범위를 넘는지 확인한다.

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

using namespace std;

int solution(vector<int> stones, int k) {
    int length = stones.size();
    int max_value = *max_element(stones.begin(), stones.end());
    // printf("%d", max_value);
    vector<vector<int>> vect(max_value+1, vector<int>(length+1, 0));
    
    /*
    for (auto v: vect) {
        printf("%d", v);
    }*/

    for (int i = 1; i <= max_value; i++) {
        for (int j = 1; j < length+1; j++) {
            if (stones[j-1] <= i) {
                vect[i][j] = vect[i][j-1] + 1;
                if (vect[i][j] >= k) {
                    return i;
                }
            }
        }
    }
}

(시도 2)

우선 스톤의 숫자가 낮은 값부터 정렬한다. 이는 돌들이 사라지는 순서를 의미한다. visited라는 벡터를 정의하여 해당 돌을 포함한 주위에 없어진 돌의 개수를 저장한다. 만약 돌이 사라지면 주변에 없는 돌의 개수를 반영하여 visited에 저장한다. 중요한 것은 없어진 돌의 개수가 업데이트 될 때마다 연결된 모든 돌에 대한 visited 값도 변경되어야한다는 것이다.

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

using namespace std;
typedef pair<int, int> p;

vector<int> visited;

bool compLogic(p a, p b) {
    return a.first < b.first;
}

void updateRight(int idx, int length, int nv) {
    visited[idx] = nv;
    if (idx < length) {
        if (visited[idx+1]) updateRight(idx+1, length, nv);
    }
}

void updateLeft(int idx, int nv) {
    visited[idx] = nv;
    if (idx > 1) {
        if (visited[idx-1]) updateLeft(idx-1, nv);
    }
}

int solution(vector<int> stones, int k) {
    int length = stones.size();
    visited.assign(length+2, 0);
    vector<p> arr;
    
    for (int i = 0; i < length; i++) {
        arr.push_back({stones[i], i+1});
    }
    sort(arr.begin(), arr.end(), compLogic);

    for (int i = 0; i < length; i++) {
        int idx = arr[i].second;
        int nv = visited[idx-1] + visited[idx+1] + 1;
        
        if (nv >= k) {     
            return arr[i].first;
        }
        updateLeft(idx, nv);
        updateRight(idx, length, nv);
    }
    
    return 0;
}