[백준] 5525번 IOIOI C++ 풀이

---

알고리즘 분류

• 문자

---

문제 설명

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

---

입력 설명

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

---

출력 설명

S에 PN이 몇 군데 포함되어 있는지 출력한다.

---

서브테스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

---

예제 입력

1
13
OOIOIOIOIIOII

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

2
13
OOIOIOIOIIOII

• OOIOIOIOIIOII
• OOIOIOIOIIOII

---

예제 출력

4

2

---

아이디어

첫 번째 시도 : n의 값에 따라서 substring을 만든 후 단순 비교 -> O(n*m) time으로 시간 초과

두 번째 시도 : string에 멤버 함수 find()를 사용하여 substring의 index를 찾는데 성공하면 count를 1씩 증가시키고 그 이후부터 계속 탐색 -> 50점 획득

세 번째 시도 : substring은 맨 처음 I가 들어간 이후 OI를 n만큼 반복함. 따라서 원본 문자열에서 OI가 n번만큼만 나오는지 체크하면 된다. -> 100점으로 성공

---

알고리즘

원본 문자열 str을 입받는다.

i가 1 ~ str.size()-1만큼 반복하는 for문을 돈다.

이렇게 범위를 잡은 이유는 str의 i-1, i, i+1을 모두 봐야 하기 때문이다.

substring의 맨 처음은 무조건 I로 시작하므로

str[i-1] = 'I'라면 비교를 시작한다.

while(str[i]=='O' && str[i+1] == 'I') 라는 조건으로 계속 반복하여 이를 만족하면 count를 1씩 증가시키고 또 다음 인덱스의 비교를 위해서 i+=2를 해준다.

이렇게 진행하다가 count가 n과 같아지는 순간이 오면 일치하는 substring을 1개 발견한 것이다.

그러면 answer를 1 증가시키고 맨 앞의 OI 세트 하나만큼을 현재 측정 중인 count에서 빼야 하므로 count에서 1을 빼준다. OI가 연속되어 나온다면 이를 반복하고 중간에 연속이 끊긴다면 count를 0으로 초기화해 주고 겉의 for 문을 반복한다.

이후 answer를 출력하면 정답이다.

---

코드

#include <iostream>
#include <string>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int n, m, ans=0;
    string str;
    cin>>n>>m>>str;
    for(int i=1;i<str.size()-1;i++)
        {
            int cnt=0;
            if(str[i-1]=='I')
            {
                while(str[i]=='O' && str[i+1] == 'I')
                    {
                        cnt++;
                        i+=2;
                        if(cnt==n)
                        {
                            cnt--;
                            ans++;
                        }
                    }
            }
        }
    cout<<ans;
    return 0;
}

---

후기

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

문제를 푸는 방법은 여러 가지지만

이 문제를 서브 테스크도 모두 통과해야 100점을 맞을 수 있기 때문에

빠른 해결 시간이 중요한 문제였다.

KMP나 라빈-카프 알고리즘을 사용하여 문제를 해결하였다면 실력 향상에 더욱 도움이 되었겠지만

아쉽게도 바로 그런 생각이 떠오르지는 않았다.

그리고 KMP는 원래 알았지만 라빈-카프는 문제를 풀려고 서칭을 하다가 처음 알게 되었다.

알고리즘의 세계는 넓고도 험난한 것 같다...

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!