[백준] 5525 - IOIOI

5525. IOIOI 풀이

난이도: Silver I
문제 주소: https://www.acmicpc.net/problem/5525

문제 풀이

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

문제를 처음 봤을때는 생각보다 어려워 보여서 풀이를 고민하는데 시간이 걸렸다
뭔가 DP를 써야할거 같이 생긴거 같아서 이쪽을 고민해보다가 바로 아닌거같아서 넘기고 다음에는 n에 해당하는 길이의 문자열이 존재하는지 문자열 전체를 순회하는 식으로 가야할까 했지만 시간복잡도 때문에 넘기고 떠올린게 투포인터였다

 

while (ed < m ) {  
    if (str[ed] != 'I' && str[st] != 'I') {  
        ed++;        
        st++;    
    }  
    if (str[ed] == 'I' && str[st] == 'I') {  
        if (ed + 2 >= m) break;  
        if (str[ed + 1] == 'O' && str[ed + 2] == 'I') {  
            ed += 2;  
            len++;            
            if (len >= n) anw++;  
        }        
        else {  
            st = ++ed;            
            len = 0;  
        }    
    } 
}

탐색을 위한 두 포인터 역할을 하는 ed와 st를 두고 현재 문자가 'I'일 때 바로 뒤의 두 문자가 'O'와 'I'인지 연속해서 확인하는 방식을 사용했다. 현재 위치에서 다음 두 문자가 'OI' 패턴이라면 탐색 위치 ed를 2만큼 증가시키고, 연속된 패턴의 길이를 의미하는 len을 1 증가시킨다. 이때 연속된 길이 len이 구하고자 하는 패턴의 반복 횟수 N 이상이 되면 완전한 PN이 만들어진 것이므로 정답 anw를 1 증가시킨다.그리고 만약 'OI' 패턴이 끊어지게 된다면 다시 새로운 'I'부터 탐색을 시작해야 하므로 st 포인터를 다음 위치로 갱신하고 연속된 길이 len을 0으로 초기화했다.

결과적으로 M번의 긴 문자열에 대해 불필요한 중복 탐색 없이 한 번의 순회만으로 답을 찾을 수 있어서 시간 지연 없이 바로바로 답이 나온다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <climits>
#include <stack>
#include <unordered_set>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unordered_map<int,int> umap;
    int n, m;
    string str;
    cin >> n >> m >> str;

    int st = 0, ed = 0;

    int len = 0;
    int anw = 0;
    while (ed < m ) {
        if (str[ed] != 'I' && str[st] != 'I') {
            ed++;
            st++;
        }

        if (str[ed] == 'I' && str[st] == 'I') {
            if (ed + 2 >= m) break;
            if (str[ed + 1] == 'O' && str[ed + 2] == 'I') {
                ed += 2;
                len++;
                if (len >= n) anw++;
            }
            else {
                st = ++ed;
                len = 0;
            }
        } 
    }

    cout << anw;
}   

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 2239 - 스도쿠  (0)	2026.04.14
[백준] 12015 - 가장 긴 증가하는 부분 수열2  (0)	2026.04.08
[백준] 11404 - 플로이드  (0)	2026.04.03
[백준] 9663 N－Queen  (0)	2026.04.01
[백준] 10814 - 나이순 정렬  (0)	2026.04.01