문제 소개
무한히 뻗은 수직선 위에 여러 개의 돌이 놓여 있다고 가정해 봅시다. 배열 stones에는 각 돌의 위치가 저장되어 있으며, stones[i]는 i번째 돌의 좌표를 나타냅니다. 이때 가장 왼쪽이나 가장 오른쪽에 위치한 돌을 '끝점 돌(endpoint stone)'이라고 부릅니다.
매 차례마다 플레이어는 끝점 돌 하나를 골라 아무 돌도 없는 빈 자리로 옮겨야 하며, 옮긴 뒤에는 그 돌이 더 이상 끝점 돌이 아니어야 합니다.
예를 들어 돌들이 [1, 2, 5]에 놓여 있다면, 위치 5에 있는 돌은 어디로 옮겨도(예: 0 또는 3) 여전히 끝점 돌이 되기 때문에 움직일 수 없습니다.
게임은 더 이상 유효한 수를 둘 수 없을 때, 즉 모든 돌이 연속된 위치에 모였을 때 종료됩니다. 따라서 게임이 끝나기까지 만들 수 있는 최소 이동 횟수와 최대 이동 횟수를 구해야 하며, 답은 [min_moves, max_moves] 형태의 쌍으로 반환합니다.
예를 들어 입력이 [7, 3, 9]라면 결과는 [1, 3]이 됩니다.
핵심 아이디어
최대 이동 횟수(max_moves)
최대한 많이 움직이려면 한쪽 끝의 돌 하나를 희생하고 나머지 범위를 최대한 활용하는 것이 유리합니다. 따라서 '첫 번째 돌을 제외한 경우'와 '마지막 돌을 제외한 경우' 중 더 넓은 구간을 선택한 뒤, 이미 차지하고 있는 (n − 2)칸을 빼주면 됩니다.
최소 이동 횟수(min_moves)
목표는 모든 돌을 길이 n짜리 연속 구간 안에 집어넣는 것입니다. 각 시작 위치 i에 대해 [a[i], a[i] + n − 1] 구간을 검사하며, 구간 밖에 남은 돌의 개수를 셉니다. 구간 내부에 이미 빈틈(gap)이 있다면 바깥의 돌을 그 빈틈으로 바로 옮길 수 있지만, 빈틈이 전혀 없다면 한 번의 추가 이동이 필요합니다.
접근 방법
이 문제는 슬라이딩 윈도우(sliding window) 기법으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
크기가 2인 정답 배열 ans를 선언하고, ans[0]은 INT_MAX, ans[1]은 INT_MIN으로 초기화합니다. n은 배열의 크기입니다.
배열 a를 오름차순으로 정렬합니다.
x := 1로 초기화한 뒤, 인접한 두 돌의 간격이 정확히 1인 동안 x를 증가시킵니다.
x == n이라면 모든 돌이 이미 연속적으로 배치된 상태이므로 {0, 0}을 반환합니다.
minVal := 0, j := 1로 설정합니다.
시작 인덱스 i를 0부터 순회하며 다음을 반복합니다.
curr := a[i], lastPossible := a[i] + n − 1로 설정합니다. lastPossible이 마지막 돌의 위치 a[n − 1]보다 크면 반복을 종료합니다.
spaceInBetween := false로 초기화합니다.
j가 i 이하라면 j := i + 1로 갱신합니다.
a[j] ≤ lastPossible인 동안 j를 증가시키며, 인접한 두 돌 사이의 간격이 1보다 크면 spaceInBetween := true로 표시합니다.
idx := j − 1로 두고, 구간 밖에 남은 돌이 2개 이상이면 spaceInBetween := true로 설정합니다.
ballLeft := i, ballRight := n − (idx + 1)로 구간 밖 돌의 개수를 구합니다.
minVal := ballLeft + ballRight + (spaceInBetween이 true면 0, 아니면 1)로 계산합니다.
ans[0] := min(ans[0], minVal)로 최소 이동 횟수를 갱신합니다.
ans[1] := max(a[n − 2] − a[0], a[n − 1] − a[1]) − (n − 2)로 최대 이동 횟수를 계산합니다.
main 함수에서 solve(stones)를 호출해 결과를 얻습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> solve(vector<int> a) {
vector <int> ans(2);
ans[0] = INT_MAX;
ans[1] = INT_MIN;
int n = a.size();
sort(a.begin(), a.end());
int x = 1;
while(x < n && a[x] - a[x - 1] == 1)
x ++;
if(x == n){
return {0,0};
}
int minVal = 0;
int j = 1;
for(int i = 0; i < a.size(); i++){
int curr = a[i];
int lastPossible = a[i] + n - 1;
if(lastPossible > a[n - 1])
break;
bool spaceInBetween = false;
if(j <= i)
j = i + 1;
while(j < n && a[j] <= lastPossible){
if((a[j] - a[j - 1]) > 1) {
spaceInBetween = true;
}
j++;
}
int idx = j - 1;
if(n - (idx - i + 1) > 1)
spaceInBetween = true;
int ballLeft = i;
int ballRight = n - (idx + 1);
minVal = ballLeft + ballRight + (spaceInBetween? 0 : 1);
ans[0] = min(minVal, ans[0]);
}
ans[1] = max(a[n - 2] - a[0], a[n - 1] - a[1]) - (n -2);
return ans;
}
vector<int> numMovesStonesII(vector<int>& stones) {
return solve(stones);
}
};
main(){
Solution ob;
vector<int> v1 = {7,3,9};
print_vector(ob.numMovesStonesII(v1));
}
실행 결과
입력:
[7,3,9]
출력:
[1, 3]
입력 [7, 3, 9]에 대해 최소 이동 횟수는 1번, 최대 이동 횟수는 3번으로 계산되며, 예상했던 결과 [1, 3]과 정확히 일치합니다. 정렬 후 슬라이딩 윈도우를 활용하면 시간 복잡도 O(n log n)(정렬 비용 포함)로 효율적으로 답을 구할 수 있습니다.