문제 소개
원 위에 n개의 주유소가 배치되어 있다고 가정해 봅시다. 각 주유소마다 다음 두 가지 데이터가 주어집니다.
- 기름의 양 — 해당 주유소에서 채울 수 있는 연료의 양
- 거리 — 현재 주유소에서 다음 주유소까지의 거리
목표는 자동차가 중간에 기름이 바닥나지 않고 원형 코스를 한 바퀴 완주할 수 있는 최초의 출발 지점을 찾는 것입니다. 계산을 단순화하기 위해 기름 1단위로 거리 1단위를 이동할 수 있다고 가정합니다.
예를 들어 주유소가 네 곳 있고, 각 주유소의 기름량과 다음 주유소까지의 거리가 [(4, 6), (6, 5), (7, 3), (4, 5)]처럼 주어졌다고 합시다. 이 경우 자동차가 원형 주행을 성공적으로 마칠 수 있는 첫 번째 지점은 두 번째 주유소입니다. 따라서 출력 결과는 start = 1(두 번째 주유소의 인덱스)이 되어야 합니다.
접근 방법: 큐(Queue) 활용
이 문제는 큐를 사용하면 효율적으로 해결할 수 있습니다. 큐에는 현재 진행 중인 순회 경로에 속한 주유소들이 저장되며, 전체 흐름은 다음과 같습니다.
- 첫 번째 주유소를 큐에 삽입한 뒤, 순회를 완료하거나 현재 남은 기름량이 음수가 될 때까지 주유소를 계속 추가합니다.
- 남은 기름량이 음수가 되면, 큐가 빌 때까지 앞쪽 주유소부터 차례로 제거하면서 새로운 출발 후보를 찾습니다.
- 출발 인덱스가 다시 0으로 돌아오면 더 이상 시도할 지점이 없다는 뜻이므로 -1을 반환합니다.
여기서 핵심 아이디어는 어떤 출발점에서 실패했다면, 그 출발점과 실패 지점 사이의 어느 곳에서 출발해도 반드시 실패한다는 것입니다. 이 성질 덕분에 모든 지점을 매번 처음부터 다시 검사하지 않고도 선형 시간 O(n) 안에 정답을 구할 수 있습니다.
C++ 구현 예제
아래 코드를 통해 동작 방식을 더 자세히 이해할 수 있습니다.
#include <iostream>
using namespace std;
class gas {
public:
int gas;
int distance;
};
int findStartIndex(gas stationQueue[], int n) {
int start_point = 0;
int end_point = 1;
int curr_gas = stationQueue [start_point].gas - stationQueue [start_point].distance;
while (end_point != start_point || curr_gas < 0) {
while (curr_gas < 0 && start_point != end_point) {
curr_gas -= stationQueue[start_point].gas - stationQueue [start_point].distance;
start_point = (start_point + 1) % n;
if (start_point == 0)
return -1;
}
curr_gas += stationQueue[end_point].gas - stationQueue [end_point].distance;
end_point = (end_point + 1) % n;
}
return start_point;
}
int main() {
gas gasArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
int n = sizeof(gasArray)/sizeof(gasArray [0]);
int start = findStartIndex(gasArray, n);
if(start == -1)
cout<<"No solution";
else
cout<<"Index of first gas station : "<<start;
}입력
[[4, 6], [6, 5], [7, 3], [4, 5]]
출력
Index of first gas station : 1
복잡도 분석
- 시간 복잡도: O(n) — 각 주유소는 삽입과 삭제 과정에서 최대 두 번씩만 처리됩니다.
- 공간 복잡도: O(1) — 실제 큐 자료구조 대신 start_point와 end_point 두 변수로 슬라이딩 윈도우를 표현하므로 추가 메모리가 필요하지 않습니다.