C++ 재귀로 풀어보는 원형 배열 문제: 두 번째 요소마다 삭제한 후 마지막에 남는 수 찾기

문제 개요

1부터 n까지의 정수가 담긴 원형 배열(circular array)이 있다고 가정해 보겠습니다. 첫 번째 요소부터 시작해 매번 두 번째 요소를 차례대로 삭제할 때, 마지막까지 남게 되는 요소를 구하는 것이 이 글의 목표입니다.

예를 들어 입력이 5라면 배열은 [1, 2, 3, 4, 5]가 됩니다. 1부터 시작해 두 번째 요소인 2를 삭제하고, 이어서 남은 요소 중 두 번째인 4를 삭제하는 방식으로 진행하면 다음과 같은 과정이 됩니다.

모든 삭제 과정이 끝난 후 배열에는 3 하나만 남습니다.

재귀를 활용한 풀이 접근

이 문제는 재귀(recursion)를 사용하면 간단하게 해결할 수 있습니다. 먼저 n이 짝수라고 가정해 보겠습니다. 이 경우 2, 4, 6처럼 짝수들이 먼저 제거되고, 다시 1부터 시작하게 됩니다. 즉, 한 바퀴에서 n/2개의 숫자가 제거되는 셈입니다.

그러면 남은 배열은 홀수만 포함하는 크기 n/2의 배열 [1, 3, 5, ...]이 되며, 여기에 동일한 규칙을 반복해서 적용할 수 있습니다. 이를 수식으로 정리하면 다음과 같습니다.

solve(n) = 2 * solve(n / 2) - 1   // n이 짝수일 때
solve(n) = 2 * solve((n - 1) / 2) + 1   // n이 홀수일 때

재귀 호출을 멈추는 기저 조건(base case)은 solve(1) = 1입니다. 매 단계마다 문제의 크기가 절반으로 줄어들기 때문에 이 알고리즘의 시간 복잡도는 O(log n)으로 매우 효율적입니다.

C++ 코드 예제

#include<iostream>
using namespace std;
int deleteSecondElement(int n) {
    if (n == 1)
        return 1;
    if (n % 2 == 0)
        return 2 * deleteSecondElement(n / 2) - 1;
    else
        return 2 * deleteSecondElement(((n - 1) / 2)) + 1;
}
int main() {
    int n = 5;
    cout << "Remaining Element: " << deleteSecondElement(n) << endl;
    n = 10;
    cout << "Remaining Element: " << deleteSecondElement(n) << endl;
}

실행 결과

Remaining Element: 3
Remaining Element: 5

n이 5일 때는 3이, n이 10일 때는 5가 최종적으로 남는 것을 확인할 수 있습니다. 이처럼 재귀 관계식을 세워두면 배열을 실제로 조작하지 않고도 로그 시간 안에 정답을 바로 계산할 수 있습니다.