백준 5525번 [IOIOI](C++)-yes6686- 티스토리

백준 문제 풀이: 5525 [IOIOI]

---

문제 링크: https://www.acmicpc.net/problem/5525

문제 설명:

길이 m의 문자열 s가 주어졌을 때, 패턴 P(n) = IOI...OI (IOI가 n번 반복되는 문자열)이 s 안에 몇 번 포함되어 있는지 계산하는 문제입니다. 연속으로 나타나는 IOI의 패턴에서 최소 n개의 IOI가 포함된 경우만 카운트합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {

    int n, m;
    string s;
    cin >> n;
    cin >> m;
    cin >> s;
    int nCnt = 0;
    int ansCount = 0;
    for (int i = 1; i < m - 1; i++) {
        if (s[i] == 'O') {
            if (s[i - 1] == 'I' && s[i + 1] == 'I') {
                nCnt++;
                if (nCnt >= n) {
                    ansCount++;
                }
                i++; // OI가 매칭된 경우 다음 I로 이동
            } else {
                nCnt = 0;
            }
        } else {
            nCnt = 0; // 패턴이 깨지면 nCnt 초기화
        }
    }
    cout << ansCount;
}

---

코드 설명

• 핵심 아이디어: 문자열 s를 순회하며 'IOI' 패턴을 탐색합니다. 패턴이 연속으로 나타나면 카운트를 누적하며, 패턴이 깨질 경우 카운트를 초기화합니다.
• 구현 세부사항:
  • nCnt: 현재까지 발견한 연속된 IOI 패턴의 개수입니다.
  • IOI 패턴이 n번 이상 발견될 때마다 ansCount를 증가시킵니다.
  • 패턴이 끝나거나 깨질 때 nCnt를 초기화합니다.
  • 패턴의 특성상, 'IOI'가 매칭되면 인덱스를 한 칸 더 건너뜁니다.
• 시간 복잡도: O(m)
  • 문자열 s를 한 번 순회하며 패턴을 찾기 때문에 선형 시간 복잡도를 가집니다.

---

결과

패턴 P(n)을 포함하는 횟수를 효율적으로 계산하며, 입력 크기가 커져도 빠르게 동작합니다. 이 코드로 정확하고 최적화된 결과를 얻을 수 있습니다.

다른 접근 방식이나 궁금한 점이 있다면 댓글로 공유해주세요!