C++로 주어진 시간 후 대기열(큐)의 배치 구하기

문제 소개

이 문제에서는 문자 'M'(남성)과 'F'(여성)로만 구성된 문자열 하나와 시간 t가 주어지며, 우리의 과제는 주어진 시간이 지난 후 대기열의 배치를 구하는 것입니다.

이 문자열은 버스에 타기 위해 한 줄로 서 있는 사람들의 대기열을 나타냅니다. 줄에 선 모든 남성들은 기사도 정신이 투철해서, 어느 시점이든 자신 바로 뒤에 여성이 서 있는 것을 발견하면 그 여성과 자리를 맞바꿉니다. 버스 탑승까지 남은 시간은 t 단위이며, 한 번의 자리 교환에는 1단위 시간이 걸립니다. 따라서 버스가 도착했을 때의 대기열 상태를 재배치를 통해 계산해야 합니다.

예제로 문제 이해하기

입력 : queue = "MFMMFF" , t = 3
출력 : FFMFMM

풀이 과정 설명 −

T = 0 → 1 동안, 1번 위치의 'M'이 2번 위치의 'F'와 자리를 바꾸고, 4번 위치의 'M'이 5번 위치의 'F'와 자리를 바꿉니다. 대기열은 "FMMFMF"가 됩니다.
T = 1 → 2 동안, 3번 위치의 'M'이 4번 위치의 'F'와, 5번 위치의 'M'이 6번 위치의 'F'와 자리를 바꿉니다. 대기열은 "FMFMFM"이 됩니다.
T = 2 → 3 동안, 2번 위치의 'M'이 3번 위치의 'F'와, 4번 위치의 'M'이 5번 위치의 'F'와 자리를 바꿉니다. 대기열은 최종적으로 "FFMFMM"이 됩니다.

해결 접근 방법

이 문제를 해결하는 가장 간단한 방법은 대기열을 나타내는 문자열을 t번 순회(traversal)하는 것입니다. 매 순회마다 연속된 "MF" 패턴을 찾아 M과 F의 위치를 서로 교환하고, 모든 순회가 끝난 뒤 최종 문자열을 반환하면 됩니다.

시간 복잡도는 O(t × n)으로, 여기서 n은 대기열의 길이입니다. 각 단위 시간마다 문자열 전체를 한 번씩 훑으면서 인접한 남성-여성 쌍을 동시에 교환할 수 있으므로, 교환이 병렬적으로 일어나는 상황을 정확히 시뮬레이션할 수 있습니다.

구현 예제

다음 프로그램은 위에서 설명한 풀이의 동작을 보여줍니다.

#include <iostream>
using namespace std;

string rearrangeQueue(int n, int t, string queue) {
    for (int i = 0; i < t; i++)
        for (int j = 0; j < n - 1; j++)
            if (queue[j] == 'M' && queue[j + 1] == 'F') {
                queue[j] = 'F';
                queue[j + 1] = 'M';
                j++; // 이미 교환된 쌍 건너뛰기
            }
    return queue;
}

int main() {
    int n = 6, t = 3;
    string queue = "MFMMFF";
    cout << "시간이 지난 후의 대기열 : " << rearrangeQueue(n, t, queue);
    return 0;
}

실행 결과

시간이 지난 후의 대기열 : FFMFMM

마무리

핵심 포인트는 내부 반복문에서 한 쌍을 교환한 뒤 j를 한 칸 더 증가시켜 j++로 다음 인덱스를 건너뛴다는 점입니다. 이는 같은 사람이 1단위 시간 안에 두 번 자리를 바꿀 수 없다는 문제의 조건을 반영한 것으로, 이 처리 덕분에 실제 상황과 동일하게 시뮬레이션이 진행됩니다.