[프로그래머스] Level 3. 징검다리 건너기

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

프로그래머스

 

정렬 이용해 풀기.

 

정렬과 포인터를 이용해 풀기

정렬을 이용해 풀때는 징검다리를 몇개 건너는지 확인하는것이 핵심이다. 이를 위해 자신의 앞인덱스를 저장하는 be와 다음 징검다리 인덱스를 저장하는 ne를 이용해 풀 수 있다.

 

내가 i번째 징검다리를 삭제했을때, 생기는 gap은 내 앞 인덱스 be[i] 와 내 뒤 인덱스 ne[i] 의 차이이다. 

그리고나서 , 내 앞뒤를 연결해주도록 수정한다.

 

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

using namespace std;

vector<bool> path;
int gap =0;

bool compare(pair<int,int>& a, pair<int,int>& b){return a.second < b.second;}

int solution(vector<int> stones, int k) {
    int answer = 0;
    vector<pair<int,int>> v;    
    vector<int> ne; vector<int> be;
    path.resize(stones.size(), true);
    
    for(int i = 0; i<stones.size(); i++){
        v.push_back(make_pair(i, stones[i]));    
        ne.push_back(i+1);
        be.push_back(i-1);
    }
    
    sort(v.begin(), v.end(), compare);
    
    for(int i=0; i<v.size(); i++){
        int cnt = v[i].second - answer;
        if(cnt>0) answer += cnt;
        
        int next = ne[v[i].first];
        int before = be[v[i].first];
        
        if(0<=next && next < be.size()) be[next]= before;
        if(0<=before&& before < be.size()) ne[before] = next;
        
        gap = max(gap,next-before-1);
        if(gap >= k) break;
    }
    
    
    return answer;
}

 

 

다른 풀이를 보던 중 슬라이딩 윈도우 알고리즘  으로 푼 사람이 굉장히 많았다. 처음들어보는거라, 공부했다.

내가 푼 방법은 시간복잡도가 O(N log N) 이지만, 슬라이딩 윈도우 알고리즘은 O(N) 이라고 한다.

 

 

슬라이딩 윈도우 개념

k크기의 윈도우(구간) 을 유지하면서 현재 구간의 최댓값을 관리한다.

각 윈도우에서 가장 적은 횟수만큼 밟을 수 있는 돌(최댓값) 이 핵심!

최댓값이 가장 작은 경우를 최대한 오래 유지한다.

 

진행방식

k길이의 윈도우를 유지한다. 

윈도우 내 최댓값을 유지하면서 다음으로 이동한다.

윈도우를 하나씩 이동하며, 현재 구간의 최댓값을 갱신한다.

가장 작은 최댓값이 정답이다.

 

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

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    deque<int> dq;

    // 초기 윈도우 설정
    for (int i = 0; i < k; i++) {
        // 새로운 값이 들어올 때, 기존 값보다 작다면 제거 (오름차순 유지)
        while (!dq.empty() && stones[dq.back()] <= stones[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }

    // 슬라이딩 윈도우 진행
    answer = stones[dq.front()];  // 첫 번째 윈도우의 최댓값

    for (int i = k; i < stones.size(); i++) {
        // 현재 윈도우에서 벗어난 요소를 제거
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }

        // 새로 들어오는 값 추가 (정렬된 형태 유지)
        while (!dq.empty() && stones[dq.back()] <= stones[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // 현재 윈도우의 최댓값 갱신 (dq.front()가 현재 윈도우에서 가장 큰 값의 인덱스)
        answer = min(answer, stones[dq.front()]);
    }

    return answer;
}

 

 

코드 원리 상세 설명

📌 슬라이딩 윈도우에 deque를 사용한 이유

• deque를 사용하면 윈도우 내 최댓값을 빠르게 관리할 수 있습니다.
• deque의 **앞(front)**에는 현재 윈도우에서 가장 큰 값의 인덱스가 위치합니다.
• deque의 **뒤(back)**에는 작은 값들이 정렬됩니다.
• 값이 새롭게 들어올 때, 기존 값보다 작다면 모두 제거하여 내림차순 유지합니다.

---

🔹 슬라이딩 윈도우 진행 과정

예제 입력:

stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]; k = 3;

윈도우 위치슬라이딩 윈도우 값최댓값최소 최댓값 (answer)

윈도우 위치	슬라이딩 윈도우 값	최댓값	최소 최댓값(answer)
[2, 4, 5]	deque: [5]	5	5
[4, 5, 3]	deque: [5]	5	5
[5, 3, 2]	deque: [5]	5	5
[3, 2, 1]	deque: [3]	3	3
[2, 1, 4]	deque: [4]	4	3
[1, 4, 2]	deque: [4]	4	3
[4, 2, 5]	deque: [5]	5	3
[2, 5, 1]	deque: [5]	5	3

최종적으로 **최소 최댓값 answer = 3**이 됩니다.

 

너무 생소한 개념이라 어렵다..