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

문제 개요

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

문제 설명

주어진 문자열에는 s와 p 두 종류의 문자만 포함되어 있습니다.

s: 신호(signal)를 나타냅니다.
p: 아직 신호가 닿지 않은 위치(position)를 나타냅니다.

신호는 s에서 시작하여 왼쪽과 오른쪽 양방향으로 동시에 전파되며, 인접한 다음 위치로 이동하는 데 1단위의 시간이 걸린다고 가정합니다. 따라서 우리의 목표는 문자열의 모든 p가 s(신호)로 변환되는 데 필요한 총 시간을 구하는 것입니다.

예시

입력 − pppppspss → 출력 − 5
입력 − pspspsps → 출력 − 1
입력 − ssssss → 출력 − 0

첫 번째 예시에서 가장 왼쪽의 신호가 연속된 5개의 p를 통과하는 데 5단위의 시간이 걸리므로 정답은 5입니다. 세 번째 예시처럼 문자열이 모두 신호(s)로 이루어져 있다면 추가 시간은 0입니다.

접근 방법 (알고리즘)

문제를 해결하는 단계는 다음과 같습니다.

문자열과 시간 변수(time = 0)를 초기화합니다.
문자열을 순회하면서 연속된 p의 개수를 세어 변수에 저장합니다.
현재 문자가 s이고, 연속된 p의 개수가 기존에 기록된 시간보다 크다면 해당 p 블록의 왼쪽에도 s가 존재하는지 확인합니다.
왼쪽과 오른쪽 양쪽 모두에 s가 있다면, 신호가 양방향으로 동시에 전파되므로 p의 개수를 절반(올림)으로 나눕니다.
p 카운트를 초기화하고 다음 블록을 처리합니다.
순회가 끝나면 계산된 최대 시간을 반환합니다.

C++ 코드 구현

#include <bits/stdc++.h>
using namespace std;
int timeToConvertToSignalString(string sample_string, int string_len) {
    int p_count = 0, time = 0;
    for (int i = 0; i <= string_len; i++) {
        if (sample_string[i] == 'p') {
            p_count++;
        }
        else {
            if (p_count > time) {
                bool is_present_left_side = false;
                if (((i - p_count) > 0) && (sample_string[i - p_count - 1] == 's')) {
                    is_present_left_side = 1;
                }
                if (is_present_left_side) {
                    p_count = ceil((double)p_count / 2);
                }
                time = max(time, p_count);
            }
            p_count = 0;
        }
    }
    return time;
}
int main() {
    string sample_string = "pppppspss";
    int n = sample_string.size();
    cout << timeToConvertToSignalString(sample_string, n) << endl;
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

다른 입력값으로 프로그램을 실행해 보면서 결과를 직접 확인해 보세요.

마무리

이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.