[프로그래머스 C++] 징검다리 건너기

 

[프로그래머스 C++] 징검다리 건너기

 

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

프로그래머스

---

 

 

해결전략

 

이분 탐색

슬라이딩 윈도우 알고리즘  Sliding Window Algorithm

---

 

 

처음 시도한 코드-  효율성 7 ~ 14 통과X

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
// 연속된 k개의 징검다리의 각각의 수가 낮은거 찾아야 함
// 처음부터 k개씩 묶은 후 가장 높은 수를 기록하며, k개씩 묶었을때 가장 큰 수의 숫자가 전체 묶음 중 가장 작은 것을 구함.
 
int solution(vector<int> stones, int k) {
    int answer = 987654321;
    
    for (int i = k-1; i < stones.size(); i++)
    {
        int maxNum = 0;
        for (int j = i; j >= i-(k-1); j--){
            maxNum = max(maxNum, stones[j]);
        }
        //cout << "maxNum = " << maxNum << "\n";
        
        answer = min(answer, maxNum);
    }
    
    return answer;
}

 

 

---

 

 

 

두번째 시도한 코드 - 효율성 13번만 통과하지 않음

 

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
 
// 연속된 k개의 징검다리의 각각의 수가 낮은거 찾아야 함
// 처음부터 k개씩 묶은 후 가장 높은 수를 기록하며, k개씩 묶었을때 가장 큰 수의 숫자가 전체 묶음 중 가장 작은 것을 구함.
 
int solution(vector<int> stones, int k) {
    int answer = 2147000000;
    vector<int> v(k, 0);
    deque<int> dQ;
    int maxNum = 0;
    
    for (int i = 0; i < k; i++){
        dQ.push_back(stones[i]);
        maxNum = max(maxNum, stones[i]);
    }
    answer = min(answer, maxNum); 
    
    for (int i = k; i < stones.size(); i++)
    {
        if (dQ.front() == maxNum) {           
            dQ.pop_front();
            dQ.push_back(stones[i]);
            maxNum = *max_element(dQ.begin(), dQ.end());
        }
        else {
            dQ.pop_front();
            dQ.push_back(stones[i]);
            maxNum = max(maxNum, stones[i]);
        }
        //cout << "maxNum = " << maxNum << "\n";        
        
        answer = min(answer, maxNum);        
    }
    
    return answer;
}

 

max_element를 사용하여 매번 최댓값을 다시 계산하기 때문에 시간 복잡도가 O(k * n) 이다.

 

---

 

 

 

정답코드

 

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
 
int solution(vector<int> stones, int k) {
    int answer = 2147000000; 
    deque<int> dQ; // 인덱스를 저장
 
    for (int i = 0; i < k; i++) { // 첫 번째 윈도우 초기화
        // 새로운 요소가 현재 deque의 마지막 요소보다 크거나 같으면 deque의 뒤에서부터 작은 요소들을 제거
        while (!dQ.empty() && stones[dQ.back()] <= stones[i]) {
            dQ.pop_back();
        }
        dQ.push_back(i);  // 현재 요소의 인덱스를 추가
    }
    answer = min(answer, stones[dQ.front()]); // 첫 번째 윈도우에서의 최댓값을 answer에 저장
    
    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);
 
        answer = min(answer, stones[dQ.front()]); // 현재 윈도우의 최댓값을 answer와 비교하여 최솟값을 갱신
    }
    
    return answer;
}

 

위의 방법

• deque를 사용하여 현재 윈도우(= k 범위 내의 징검다리)의 최댓값의 인덱스를 저장.
• 새로운 요소를 추가할 때마다 deque의 뒤에서부터 현재 요소보다 작은 요소를 제거.
• deque의 앞쪽에 있는 인덱스가 윈도우 밖에 있는지 확인하고 제거.

---

 

 

 

다른 사람들이 푼 이분탐색 풀

 

https://tnwlswkd.tistory.com/111

[프로그래머스] 징검다리 건너기(C++)

 

https://0xd00d00.github.io/2021/08/02/stepping_stone.html

[프로그래머스][C++][KAKAO] 징검다리 건너기 - 널두

 

 

---