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

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

✍️ 첫번째 접근

효율성을 생각하지 않고 제한사항을 제대로 확인하지 않는다면, 무작정 순회하면서 각 돌의 값을 -1을 계속 진행하는 과정을 생각할 수 있다. 하지만 이는 비효율적이다.
필자는 어쨌든간에 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수가 K개 이므로 K만큼의 범위를 넘어서지 못한다는 점에 주목했다. 슬라이딩 윈도우 기법으로 K만큼의 범위에서 합이 제일 적은 것 그리고 그 범위 중 가장 큰 값을 답이라고 생각하였지만 틀렸다는 결과를 받았다.

import Foundation

func solution(_ stones:[Int], _ k:Int) -> Int {
    var minValue = 0x3f3f3f3f
    var idx = -1
    for i in 0..<stones.count {
        if i+k-1 >= stones.count {
            break
        }
        var sum =  Array(stones[i...i+k-1]).reduce(0,+)
        if minValue > sum {
            minValue = sum
            idx = i
        }
    }
    return Array(stones[idx...idx+k-1]).max()!
}

✍️ 두번째 접근

아래와 같은 반례로 인해 필자의 첫번째 접근은 틀렸다.

K=3
555229

"555"에서 합이 15이고, "229"에서 합이 13이다. 첫번째 접근처럼 했다면, "229"의 합이 더 작으므로 정답은 9가 된다. 하지만 정답은 5이므로 잘못된 접근임을 알 수 있다.
따라서 이와 같은 접근 말고 K만큼의 범위를 돌면서 그 중 가장 큰 값을 구하고, 그 가장 큰 값들 중 가장 작은 값을 구하는 방식으로 하였다. 또한 언어를 C++로 바꿨는데 정확성 테스트케이스는 맞지만 효율성에서 시간 초과라는 결과를 받았다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0x3f3f3f3f;
    for(int i = 0; i < stones.size(); ++i) {
        if(i+k-1 >= stones.size())
            break;
        int maxValue = -1;
        for(int j = i; j < i+k; ++j) {
            if(maxValue < stones[j])
                maxValue = stones[j];
        }
        if(answer > maxValue)
            answer = maxValue;
    } 
    return answer;
}

✍️ 세번째 접근

아무래도 K만큼의 범위를 돌면서 중복되어 계산되는 값이 있는데 이에 대한 연산을 재사용하지 않아서 발생했다고 판단했다. 그리고 추가적으로 계속해서 K만큼의 범위에서 최댓값을 찾는 연산을 하지 않기 위해 grater를 사용해 내림차순으로 정렬되게 하여 그 첫번째에 해당하는 값이 최댓값이라고 계산했다. answer 변수와 현재 얻은 최댓값 중 더 작은 값이 answer라고 판단함으로써 해결했다.
이 문제로 얻은 점은 제대로된 슬라이딩 윈도우를 사용하려면 재사용할 수 있는 부분은 재사용하자는 것이고 주어진 자료형을 잘 활용하자는 것이다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    multimap<int,int,greater<int>> mp;
    multimap<int, int>::iterator iter;
    
    for(int i = 0; i < k; ++i)
        mp.insert({stones[i],i});
    
    answer = mp.begin()->first;
    
    for(int i = 0; i < stones.size(); i++) {
        if(i+k >= stones.size())
            break;
        iter = mp.find(stones[i]);
        mp.erase(iter);
        mp.insert({stones[i+k],i+k});
        answer = min(answer,mp.begin()->first);
    }
    
    return answer;
}