Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

더 이상 새로 화나는 학생이 생기지 않는 최소 시간을 계산하는 C++ 프로그램

문제 이해하기

길이가 n인 문자열 S가 주어집니다. 문자열은 'A'와 'P' 두 종류의 문자로만 구성되어 있으며, 한 줄로 서 있는 n명의 학생을 나타냅니다. S[i]가 'A'면 i번째 학생은 화난 상태이고, 'P'라면 평온한 상태입니다.

매 분마다 화난 학생(i번째)은 바로 오른쪽에 있는 평온한 학생(i+1번째)을 때립니다. 맞은 학생은 그 순간 화나게 되고, 이후 같은 방식으로 다음 학생에게 영향을 줍니다. 단, 가장 마지막에 선 학생은 아무리 화가 나 있어도 때릴 상대가 없습니다. 우리가 구해야 할 값은 더 이상 새로운 학생이 화나지 않게 되기까지 걸리는 최소 시간(분)입니다.

예시

입력이 S = "PPAPP"라고 가정해 봅시다. 이때 출력은 2입니다.

  • 1분 후: "PPAAP"
  • 2분 후: "PPAAA"

2분이 지나면 모든 학생이 화난 상태가 되고, 그 이후에는 새로 화나는 학생이 없으므로 정답은 2입니다.

해결 접근 방법

핵심 아이디어는 간단합니다. 어떤 'A' 바로 뒤에 연속된 'P'가 k개 있다면, 그 'P'들이 하나씩 차례로 화나는 데 정확히 k분이 걸립니다. 따라서 전체 문자열에서 'A' 뒤에 이어지는 연속된 'P' 구간 길이의 최댓값이 곧 정답이 됩니다.

이를 위해 문자열을 오른쪽에서 왼쪽으로 탐색하며 다음 단계를 수행합니다.

  1. n := 문자열 S의 길이로 설정
  2. ans := 0, cnt := 0으로 초기화
  3. i를 n-1부터 0까지 1씩 감소시키며 반복:
    • S[i]가 'P'이면 cnt를 1 증가
    • S[i]가 'A'이면 ans = max(ans, cnt)로 갱신한 뒤 cnt를 0으로 초기화
  4. ans 반환

C++ 코드 구현

아래 구현 예제를 통해 더 쉽게 이해할 수 있습니다.

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

int solve(string S) {
    int n = S.size();
    int ans = 0, cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (S[i] == 'P') {
            cnt++;
        } else {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    return ans;
}
int main() {
    string S = "PPAPP";
    cout << solve(S) << endl;
}

입력

PPAPP

출력

2

복잡도 분석

시간 복잡도: O(n) — 문자열을 한 번만 순회하므로 매우 효율적입니다.
공간 복잡도: O(1) — 추가 변수 두 개만 사용하므로 메모리 사용량이 일정합니다.