[백준] #5525 IOIOI🔘

• 백준 # 5525 IOIOI
• 사용 언어 : C++
• 난이도 : 실버Ⅰ🥈

문제

문제는 간단하다. 우선 I와 O로 이루어진 문장과 N, M값이 주어진다. 이때, 주어진 문장에서 $P_N$이 몇번 나오는지 출력하는 문제이다.

이 문제의 경우, 제한 조건에 따라 받을 수 있는 점수가 달랐다.

예제 입력

분석

문제 분석

우리는 IOI라는 패턴을 우선 찾아야한다. 이때, IOI패턴의 속에서 N만큼씩 몇번 반복하는지를 알아야한다.
만약 주어진 문장이 IOIOIOI이고, N=2라면,

IOIOIOI
IOIOIOI

이렇게 두 가지가 나온다.
IOIOIOI 의 두번째 I 부터 세번째 I까지의 구간은 중복되어서 세어지는 것을 확인할 수 있다.
이를 통해, 문자들은 한번만 세야 하는 것이 아니라, 패턴에 포함되어있고 패턴내에서의 위치만 다르다면 중복해서 세어주어야 한다는 것을 알 수 있다.

패턴의 반복 횟수

또한, IOI라는 패턴이 몇번 반복되는지 안다면 $P_N$이 몇 번 나오는 지도 알 수 있다.
예시로 든 문장의 길이는 7이고, 이 문장에서는 IOI패턴만이 반복되고 있다. IOI 패턴의 반복 횟수는 O의 등장 횟수와 같고, O의 경우 문장길이의 약 절반을 차지하고 있다. (O개수 = 3)

이것을 규칙으로 만들어보자.
IOI 패턴만이 반복되는 경우, 문자열의 길이 / 2의 몫은 IOI 패턴의 개수가 된다.

IOI 패턴의 개수 =[ 문자열의 길이 / 2 ]의 몫

이제, IOI 패턴의 개수와 $P_N$의 개수의 연관성을 찾아보자.

예시의 IOI 패턴 개수는 3이다.
만약 N=1이라면, $P_N$ 은 3번 나타난다.
만약 N=2이라면, $P_N$ 은 2번 나타난다.
만약 N=3이라면, $P_N$ 은 1번 나타난다.

$P_N$의 개수는 IOI 패턴 개수 - (N-1)과 동일하다는 규칙을 찾을 수 있다.

$P_N$의 개수 = IOI 패턴 개수 - (N-1)

찾아야할 것

그렇다면 우리는 주어진 문장에서 무엇을 찾아야할까?
우선 IOI가 연속된 구간들을 알아야할 것이다.
이 구간을 안다면, 구간마다 앞에서 찾아낸 규칙을 적용하여, 총 $P_N$의 개수를 알아낼 수 있을 것이다.

구현

IOI가 연속된 구간을 찾기 위해서, 스택을 사용할 것이다.
우리는 주어진 문장을 한 문자씩 읽으면서, IOI의 패턴과 일치하는지 아닌지를 판단해야 한다. 내가 현재 읽고 있는 문자가 패턴에 적합한지를 알기 위해서는 이전 문자가 무엇인지 알아야한다.

따라서, 문자를 읽은 후, 스택의 top을 조회하여 현재 문자를 스택에 넣었을 때 IOI 패턴을 유지할 수 있는지를 확인할 것이다.

만약 IOI 패턴을 유지할 수 없는 문자라면, 더이상 IOI 패턴의 연속된 구간이 아니라는 의미이므로, 스택에 있는 연속된 IOI 패턴들에서 $P_N$의 개수를 구하고, 스택을 비울 것이다.

문자를 스택에 넣을지 말지 결정하는 규칙은 아래와 같이 설정하였다.

• 현재 읽은 문자가 O인 경우
  - 스택의 top이 I➡ 규칙 만족 ⭕: 스택에 push
  - 스택이 비어있음 ➡ 규칙 불만족 ❌ : 그냥 버리기
  - 스택의 top이 O➡ 규칙 불만족 ❌ : 스택에 있는 O 제거 후, $P_N$ 개수 계산 & 스택 비우기
  
  
• 현재 읽은 문자가 I인 경우
  - 스택이 비어있음 ➡ 규칙 만족 ⭕: 스택에 push
  - 스택의 top이 O➡ 규칙 만족 ⭕: 스택에 push
  - 스택의 top이 I ➡ 규칙 불만족 ❌ : $P_N$ 개수 계산 & 스택 비우기

코드

위의 구현 사항을 아래와 같이 작성하였다.

#include <iostream>
#include <stack>

using namespace std;

int cnt=0;
int N,M;
int i;
char c;
stack<char> s;
void count();
int main()
{
    cin >> N;
    cin >> M;
    
    for(i=0;i<M;i++){
       cin >> c;
       
       if(c=='O'){ // 현재 문자가 O인 경우 
            if (s.empty()) // 스택이 빈 경우 
                continue;
            else if(s.top() == 'I') // 스택의 top이 I인 경우
               s.push(c);
            else{ // 스택의 top이 O인 경우
                s.pop();
                count();
            }
           
       }else{ //  현재 문자가 I 인 경우 
            if(!s.empty() && s.top()=='I' )  // 스택이 비어있거나 top이 I인 경우 
                count();
           
            s.push(c);
       }
       
    }
    
    if(!s.empty()){
        if(s.top()=='I')
        count();
        else{
            s.pop();
            count();
        }   
    }
    cout<<cnt;

    return 0;
}

void count(){
    int pNum  = s.size()/2-(N-1) ;
    if(pNum>0)
        cnt+=pNum;
    s = stack<char>();
}

실수했던 부분

위의 코드는 수정 후의 코드이다.
수정 전 코드에서 간과했던 부분들을 짚고 넘어가고자 한다.

1. count 함수

위에서 문제를 분석할 때, $P_N$을 계산하는 식을 작성했었다.

$P_N$의 개수 = IOI 패턴 개수 - (N-1)

이 내용을 count함수로 구현하였다.

void count(){
    int pNum  = s.size()/2-(N-1) ;
    cnt+=pNum;
    s = stack<char>();
}

그런데 이 수식에서 주의해야 할 점은, IOI 패턴 개수가 N-1보다 작을 수도 있다는 것이다.
따라서, 별도의 조건없이 작성하면 $P_N$의 개수가 음수가 나오게 되고, 당연히 틀린 결과를 얻게 된다.
따라서, $P_N$가 음수가 될 경우 전체 결과에 반영이 안되도록 수정하였다.

void count(){
    int pNum  = s.size()/2-(N-1) ;
    if(pNum>0)
        cnt+=pNum;
    s = stack<char>();
}

이처럼 어떠한 규칙을 수식으로 작성할 때는, 그 식이 예외적인 결과를 배출하지는 않는지 고려를 꼼꼼히 해보아야 한다.

2. 런타임 에러

코드 실행 중 무언가 오류가 발생한 상황이다.
디버깅을 통해, 스택의 접근 중 잘못된 부분이 있다는 사실을 확인했다.
나의 로직에는 스택의 top을 조회하는 부분이 존재한다.
그러나 스택이 비어있는 경우, top을 조회하게 되면 오류가 발생한다.

if (s.empty()) // 스택이 빈 경우 
	continue;
else if(s.top() == 'I') // 스택의 top이 I인 경우
	s.push(c);
else // 스택의 top이 O인 경우
{ 
	s.pop();
	count();
}

따라서 위와 같이 empty여부를 판단하는 조건을 먼저 배치해주어야 오류가 발생하지 않게 된다.

느낀 점

규칙을 찾는 문제는 예외사항을 완벽하게 처리하는 방법을 잘 생각하면 한방에 풀리지만, 여기저기 빈 구석들이 존재하면 한없이 틀리는 문제인 것 같다.
🌟 내가 생각하는 것보다 더 꼼꼼하게 생각하기!