문제 설명
1부터 n까지의 정수가 오름차순으로 정렬된 리스트가 있다고 가정해 봅시다. 이 게임의 규칙은 다음과 같습니다.
먼저 왼쪽에서 오른쪽으로 진행하며, 첫 번째 숫자부터 시작해 하나 걸러 하나씩 숫자를 제거합니다. 즉, 리스트 끝에 도달할 때까지 첫 번째, 세 번째, 다섯 번째… 숫자를 차례로 지웁니다.
그다음에는 오른쪽에서 왼쪽으로 방향을 바꿔, 남은 숫자들 중 맨 오른쪽 숫자부터 하나 걸러 하나씩 다시 제거합니다.
이 과정을 방향을 계속 번갈아 가며 반복하여, 마지막에 단 하나의 숫자만 남을 때까지 진행합니다.
길이가 n인 리스트로 시작했을 때 최종적으로 남는 숫자를 찾는 것이 목표입니다.
예시: n = 9일 때
입력이 n = 9라면 각 단계는 다음과 같이 진행됩니다.
1, 2, 3, 4, 5, 6, 7, 8, 9 → 왼쪽에서 오른쪽으로 제거 후: 2, 4, 6, 8
2, 4, 6, 8 → 오른쪽에서 왼쪽으로 제거 후: 2, 6
2, 6 → 왼쪽에서 오른쪽으로 제거 후: 6
마지막으로 남은 숫자는 6입니다.
따라서 정답은 6입니다.
접근 방법
매번 실제 리스트를 만들어 시뮬레이션하면 비효율적입니다. 대신 네 가지 변수만 추적하면 O(log n) 시간 안에 답을 구할 수 있습니다.
head: 현재 남아 있는 수열의 첫 번째 값 (초기값 1)
step: 한 단계에서 인접한 두 원소 사이의 간격 (초기값 1)
rem: 아직 남아 있는 원소의 개수 (초기값 n)
left: 현재 제거 방향이 왼쪽→오른쪽인지 여부를 나타내는 플래그
각 반복 단계에서는 다음 규칙을 적용합니다.
제거 방향이 왼쪽→오른쪽이거나, 남은 원소의 개수가 홀수라면 첫 번째 원소(head)가 반드시 제거되므로 head를 다음 원소로 옮깁니다. 즉, head := head + step
step := step * 2 — 매 단계마다 원소 간격은 두 배가 됩니다.
left := !left — 제거 방향을 반대로 전환합니다.
rem := rem / 2 — 한 번의 제거가 끝나면 남는 원소는 절반이 됩니다.
rem이 1이 되면 head가 곧 마지막으로 남는 숫자이므로 이를 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lastRemaining(int n) {
int head = 1;
int step = 1;
int rem = n;
int left = 1;
while(rem > 1){
if(left || rem % 2 == 1){
head += step;
}
step *= 2;
left = !left;
rem /= 2;
}
return head;
}
};
main(){
Solution ob;
cout << (ob.lastRemaining(9));
}입력
9
출력
6
복잡도 분석
매 반복마다 rem이 절반씩 줄어들기 때문에 시간 복잡도는 O(log n)이며, 추가 공간을 상수 크기만 사용하므로 공간 복잡도는 O(1)입니다. 이 덕분에 n이 매우 큰 경우에도 빠르게 정답을 계산할 수 있습니다.