문제 설명
정확히 n개의 좌석이 있는 비행기에 n명의 승객이 탑승한다고 가정해 보겠습니다. 이때 첫 번째 승객은 항공권을 분실하여 자리에 상관없이 무작위로 좌석을 선택합니다.
그 후 나머지 승객들은 다음과 같은 규칙에 따라 자리를 찾아갑니다.
- 자신의 항공권에 적힌 좌석이 아직 비어 있다면, 그 좌석에 앉는다.
- 자신의 좌석이 이미 다른 사람에게 차지되어 있다면, 남은 좌석 중에서 무작위로 하나를 선택한다.
우리가 구해야 할 것은 바로 n번째 승객이 자신의 원래 좌석에 앉을 확률입니다.
예를 들어 입력이 2라면 출력은 0.5가 됩니다. 첫 번째 승객이 1번 좌석에 앉았을 경우 두 번째 승객은 반드시 2번 좌석에 앉게 되지만, 첫 번째 승객이 2번 좌석을 가져가면 두 번째 승객은 자기 자리에 앉지 못하기 때문입니다.
접근 방법
이 문제는 언뜻 복잡해 보이지만, 사실 매우 간단한 규칙으로 해결됩니다.
- n이 1이면 유일한 승객이므로 무조건 자기 좌석에 앉으므로 1을 반환한다.
- n이 1보다 크면 0.5를 반환한다.
왜 답은 항상 0.5일까?
핵심은 첫 번째 승객의 선택에 있습니다. 첫 번째 승객이 1번 좌석을 고르면 이후 모든 승객은 자기 자리에 앉을 수 있고, n번 좌석을 고르면 n번째 승객은 절대 자기 자리에 앉지 못합니다. 만약 중간 좌석(k번)을 고르면, k번째 승객부터 같은 상황이 반복되며 결국 문제는 1번 좌석과 n번 좌석 중 누가 먼저 선택되느냐로 귀결됩니다. 이 두 사건은 대칭적이므로 확률은 정확히 0.5가 됩니다.
C++ 구현 예제
다음 코드를 통해 더 잘 이해해 보겠습니다.
class Solution {
public:
double nthPersonGetsNthSeat(int n) {
if (n == 1) return 1;
return 0.5;
}
};입력
2
출력
0.50000
마무리
이 문제는 직관적으로는 복잡한 확률 계산이 필요해 보이지만, 논리적 대칭성을 파악하면 O(1) 시간 복잡도로 해결되는 아주 우아한 문제입니다. 코딩 인터뷰에서 확률과 논리적 사고력을 동시에 평가하는 대표적인 유형이니 꼭 기억해 두세요.