[C#] 백준 5525번 문제풀이

문제번호: 5525

문제명: IOIOI

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

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

오늘은 문자열태그 문제를 풀어보았습니다.

저는 처음에 코드를 2중 for문으로(i, j) 풀이했습니다.

 i에서는 각 문자열을 하나씩 접근하고, j에서 i에서 접근한 문자를 0번 인덱스로 삼아 0번 인덱스를 기준으로 O가 N이 나올 수 있는 문자만큼 검사하여 IOI형식을 만족하는지 확인합니다. 그 후에 총 COUNT를 출력하는 방식을 사용하였습니다.

 

이 방식은 시간초과를 발생시켰습니다(50점). 시간 복잡도가 O(MXN)이었기 때문입니다.

사실 처음 코드를 작성할때도 시간초과를 걱정하긴 했었지만 단일반복문으로 끝낼 방법이 생각나지 않아서 2중 for문으로 시도해 보았지만 당연하게도 실패했습니다.

 

그래서 쩔수없이 단일 for문으로 해결할 방법을 생각해 보았습니다.

for문 내부에서 if문으로 중간 문자를 기준으로 앞, 뒤를 검사하여 IOI형식인지를 검사하고 앞으로 나아가며 IOI가 N만큼 연결된 것을 확인하면 count를 증가시키는 로직으로 작성하였고, 정답이었습니다.

다음은 정답코드입니다.

 

public static void Main()
{
    int N = int.Parse(Console.ReadLine()); // O가 포함되어야하는 개수
    int M = int.Parse(Console.ReadLine()); // 문자열의 총 길이
    string S = Console.ReadLine();

    int ioCount = 0;
    int count = 0;

    for (int i = 1; i < M - 1; i++)
    {
        if (S[i - 1] == 'I' && S[i] == 'O' && S[i + 1] == 'I')
        {
            ioCount++;
            if (ioCount >= N) count++;
            i++;
        }
        else
        {
            ioCount = 0;
        }
    }

    Console.WriteLine(count);
}