[Python][C++] 5525번 IOIOI

문제

https://www.acmicpc.net/problem/5525

 

 

코드

1. Python

# 입력 받기
n = int(input())
m = int(input())
s = input()

cnt = 0  # 패턴이 나타나는 횟수를 저장할 변수
i = 0  # 현재 문자열의 인덱스

# 문자열을 순회하면서 패턴을 찾기 위한 반복문
while i < (m - 1):
    # 현재 부분 문자열이 "IOI"와 일치하는지 확인
    if s[i:i + 3] == "IOI":
        k = 0  # 현재 연속된 "IOI" 패턴의 횟수 초기화
        # 연속된 "IOI" 패턴이 존재하는 동안 계속 탐색
        while i + 2 < m and s[i:i + 3] == "IOI":
            k += 1  # "IOI" 패턴의 수를 증가시킴
            i += 2  # "IOI" 패턴은 2칸씩 증가하므로 인덱스를 2씩 증가시킴
        # 연속된 "IOI" 패턴의 수가 N 이상일 경우
        if k >= n:
            cnt += k - n + 1  # 가능한 패턴의 시작점 수만큼 카운트를 증가시킴
    else:
        i += 1  # "IOI" 패턴이 아닐 경우 다음 인덱스로 이동

# 최종적으로 패턴이 몇 번 나타났는지 출력
print(cnt)

 

2. C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    int cnt = 0;  // 찾은 패턴의 개수를 저장할 변수
    int i = 0;  // 문자열 s를 순회할 인덱스

    // 문자열 s를 탐색하면서 패턴을 찾는 루프
    while (i < m - 1) {
        // 현재 위치에서 "IOI" 패턴이 시작되는지 확인
        if (s.substr(i, 3) == "IOI") {
            int k = 0;  // 연속된 "IOI" 패턴의 개수를 세기 위한 변수
            // "IOI" 패턴이 연속으로 나오는 동안 반복
            while (i + 2 < m && s.substr(i, 3) == "IOI") {
                k++;  // "IOI" 패턴을 찾을 때마다 증가
                i += 2;  // 다음 "IOI" 패턴을 찾기 위해 인덱스 2만큼 이동
            }
            // 연속된 "IOI" 패턴의 개수가 n 이상일 때, 가능한 패턴의 개수 계산
            if (k >= n) {
                cnt += k - n + 1;  // 가능한 패턴의 개수를 cnt에 추가
            }
        } else {
            i++;  // "IOI" 패턴이 아니면 인덱스를 1만큼 증가
        }
    }

    cout << cnt << endl;  // 최종적으로 찾은 패턴의 개수를 출력

    return 0;
}

 

 

풀이 

 

1. 패턴 분석:
   • 패턴 Pn은 I로 시작하고, 그 뒤에 (O, I)가 N번 반복되는 구조
   • 즉, 패턴의 길이는 2 * N + 1
2. 패턴 찾기:
   • 문자열 S를 순회하며, 패턴을 찾는 방식으로 해결 가능
   • 단순히 모든 위치에서 패턴을 확인하는 것은 비효율적이므로, 탐색을 최적화하는 방법이 필요함
3. 효율적인 탐색 방법:
   • 문자열 S를 한 번 순회하면서, IOI 패턴이 연속적으로 몇 번 등장하는지를 체크
   • I를 발견하면, 그 뒤에 O와 I가 반복되는지를 확인
   • IOI가 반복되는 부분이 있다면 그 부분의 시작점부터 끝까지 패턴이 몇 번 포함되는지 카운트