C++로 신호가 문자열의 모든 위치에 도달하는 데 걸리는 시간 구하기

이 튜토리얼에서는 신호가 문자열의 모든 위치에 도달하는 데 걸리는 시간을 구하는 프로그램을 C++로 작성해 보겠습니다.

문제 개요

'x'와 'o'로만 구성된 문자열이 주어집니다. 신호는 'x' 위치에서 발생하여 왼쪽과 오른쪽 두 방향으로 동시에 전파되며, 1단위 시간마다 인접한 'o' 하나를 'x'로 바꿉니다. 우리의 목표는 문자열 전체가 'x'로 변환되기까지 필요한 총 시간을 계산하는 것입니다.

접근 방법

핵심 아이디어는 연속된 'o'로 이루어진 각 구간(블록)을 기준으로 생각하는 것입니다.

블록의 양쪽 끝에 'x'가 있는 경우: 신호가 양방향에서 동시에 진행되므로, 필요한 시간은 블록 길이를 2로 나눈 후 올림한 값입니다.
블록의 한쪽에만 'x'가 있는 경우(또는 문자열 경계에 붙어 있는 경우): 신호가 한 방향으로만 진행되므로, 블록 전체 길이만큼의 시간이 필요합니다.

모든 블록에 대해 계산한 값 중 최댓값이 곧 전체 문자열을 'x'로 채우는 데 걸리는 시간이 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 신호가 모든 위치에 도달하는 데 필요한 총 시간 계산
int findMaximumDuration(string s, int n) {
    int right = 0, left = 0;
    int count = 0, maximumLength = INT_MIN;
    s = s + '1'; // 반복문 처리를 위한 종료 마커 추가
    for (int i = 0; i <= n; i++) {
        if (s[i] == 'o')
            count++; // 연속된 'o' 개수 세기
        else {
            if (count > maximumLength) {
                right = 0;
                left = 0;
                if (s[i] == 'x') // 블록 오른쪽에 'x'가 있는지 확인
                    right = 1;
                if (((i - count) > 0) && (s[i - count - 1] == 'x')) // 블록 왼쪽에 'x'가 있는지 확인
                    left = 1;
                count = ceil((double)count / (right + left));
                maximumLength = max(maximumLength, count);
            }
            count = 0;
        }
    }
    return maximumLength;
}

int main() {
    string str = "xooxoooxxoooxoooxooxooox";
    int length = str.size();
    cout << findMaximumDuration(str, length);
    return 0;
}

출력 결과

코드 설명

위 코드의 동작 과정을 단계별로 살펴보겠습니다.

문자열 끝에 임의의 마커 문자('1')를 추가하여, 마지막 'o' 블록도 반복문 안에서 자연스럽게 처리되도록 합니다.
문자열을 순회하면서 연속된 'o'의 개수를 셉니다.
'o'가 아닌 문자를 만나면 지금까지 센 블록에 대해 다음을 수행합니다.
- 블록 오른쪽과 왼쪽에 'x'가 존재하는지 각각 확인합니다.
- 양쪽에 'x'가 있으면 블록 길이를 2로 나누어 올림하고, 그렇지 않으면 블록 길이 그대로 사용합니다.
각 블록의 소요 시간 중 최댓값을 maximumLength에 저장한 뒤 반환합니다.

시간 복잡도는 문자열을 한 번만 순회하므로 O(n)이며, 공간 복잡도는 O(1)로 매우 효율적입니다.