[프로그래머스] 마법의 엘리버이터

이 포스트는 프로그래머스 사이트의 마법의 엘리베이터 문제 풀이입니다.

문제

해결 과정

이 문제를 처음 읽었을 때, 현재 위치(‘storey’층)에서 목표 위치(‘0’층)로 이동하는 경로 중
최단 경로를 구하는 문제라고 이해했습니다.
그리고 예제에서 알 수 있듯이, 0층으로 이동하는 최단 경로는 반드시 아랫쪽만 이동해서
구할 수 있는 것이 아니라 윗층으로 이동 후 마법의 버튼을 이용해 더 짧게 이동할 수 있습니다.

마법의 버튼은 \(-10^9\) 부터 \(10^9\) 까지 존재할 수 있으므로
버튼으로 이동할 층의 유효성을 고려하지 않았을 때, 경우의 수는 18가지 입니다.

따라서 마법의 버튼 사용 횟수가 가장 낮은 것을 우선적으로 연산하는 우선순위 큐 기반
다익스트라 최단거리 알고리즘을 사용해 storey층에서 0층까지의 최단거리를 구하고자 하였습니다.

첫 번째 시도 (다익스트라를 이용한 풀이)

#include <vector>
#include <cmath>
#include <queue>

#define MAX 100'000'001

using namespace std;

int solution(int storey) {
    vector<int> button;
    for(int i = 0; i <= 9; ++i) {
        button.emplace_back(pow(10, i));
        button.emplace_back(-1 * pow(10, i));
    }

    vector<int> stone_cnt(MAX, MAX);
    stone_cnt[storey] = 0;

    // C++에서 제공하는 우선순위 큐는 최대힙 기반이므로  
    // 최소힙으로 사용하기 위해서는 추가 설정이 필요
    priority_queue<pair<int, int>, 
                    vector<pair<int, int>>,     
                    greater<pair<int, int>>> pq;
    pq.push(make_pair(0, storey));
    
    while(false == pq.empty()) {
        int cost = pq.top().first;
        int curr = pq.top().second;
        pq.pop();
        
        if(curr == 0) {
            return cost;
        }
        for(const int& value : button) {
            int next = curr + value;
            
            // 층의 범위 확인
            if(next < 0 || next >= MAX)
                continue;
            // 도달한 층까지 사용한 버튼 수가 최소인지 확인
            if(stone_cnt[next] <= cost + 1)
                continue;
            stone_cnt[next] = cost + 1;
            pq.push(make_pair(cost + 1, next));
        }
    }
    return -1;
}

제출 결과 (다익스트라 기법)

그러나 실행 결과 실행 시간 초과가 일어났습니다.

각 문제의 실행 시간을 보면 대부분 1초에 가까운 실행시간을 보여주고 있습니다.
이를 통해서 코드의 최적화, 문법 오류와 같은 표면적인 문제가 아닌
알고리즘 자체가 오래 걸리기 때문에 다익스트라 알고리즘이 아닌
다른 알고리즘을 사용해야 한다는 것을 유추해 볼 수 있었습니다.

문제를 다시 분석하던 중 이 문제가 그리디 알고리즘의 대표 예제인
‘최소의 동전으로 거스름돈 주기’ 문제와 매우 유사하다는 것을 알게 되었습니다.

동전 거스름돈 문제처럼 storey층에서 이동할 때, 매번 최선의 방법을 선택하는 방법을 사용하면
다익스트라 알고리즘 보다 짧은 시간에 결과를 도출할 수 있다고 생각했습니다.

이 문제에서는 그리디 기법에서는 선택지 마다 최선의 방법을 선택해야 하므로
1의 자리와 10의 자리 값을 통해 최소한의 버튼으로 이동하는 방법을 구하고자 하였습니다.

두 번째 시도 (그리디 기법을 사용한 풀이)

#include <vector>

using namespace std;

int solution(int storey) {
    int answer = 0;
    while(storey > 0) {
        int ones_place = storey % 10;       // 일의 자리수
        int tens_place = storey / 10 % 10;  // 십의 자리수
        
        // 일의 자리가 6 이상이거나, 일의 자리수와 십의 자리수가 모두 5 이상인 경우
        if(ones_place > 5 || (ones_place >= 5 && tens_place >=5)) {
            storey += (10 - ones_place);
        } else {
            storey -= ones_place;
        }
        
        // 일의 자리수를 사용했으므로 제거
        storey /= 10;
        // 1씩 이동하였으므로 최소한으로 이동한 값을 answer에 누적
        answer += min(10 - ones_place, ones_place);
    }
    return answer;
}

제출 결과 (그리디 기법)