[백준] 5525 IOIOI (java)문제풀이

 

어떻게 문제를 풀 것인가?

-> 문자열에 포함된 IOI의 갯수를 모두 count하면 그것이 N이다

P1 : IOI

P2: IOIOI

N의 값을 입력받아 전체 제공되는 문자열에 P(N) 값을 찾아주면 된다.

-> 근데 어떻게 효율적으로 찾을 수 있을까??

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Baek5525 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        String s = br.readLine();

        int cnt = 0;
        int answer = 0;
        
        for (int i = 1; i < m - 1; i++) {
            if (s.charAt(i - 1) == 'I' && s.charAt(i) == 'O' && s.charAt(i + 1) == 'I') {
                cnt++;
                if(cnt==n){
                    cnt--;
                    answer++;
                }
                i++;
            }else{
                cnt=0;
            }
        }
        System.out.println(answer);
    }
}
//IOIOIOI

 

소스코드를 보고 이해하면 가장 좋겠지만, 솔직히 본인도 이해하는데 오래 걸렸다. 하지만 핵심을 항상 기억하면서 코드를 작성하자

for문을 한번 순회하면서 입력으로 제공된 pN을 찾을 수 있다면 가장 효율적이지 않겠나? O(N)의 시간복잡도를 가질 수 있다.