백준 5525번 : IOIOI 자바

🧫 문제 분석

 

✔️ 출처

IOIOI 실버 1

📖 문제

주어진 문자열에서 IOI 패턴으로 나오는 문자열의 개수를 찾는 문제이다.

 

몰랐는데 서브태스크는  여러가지 채점 방식이 있나보다. 배점이 50점 2개가 있다. 

 

처음에는 match를 썼다가 너무 오래걸려서 50점 받았다. 

 

IOI를 찾고 카운팅 + 1 하고 현 위치에서 +2로 이동한 후 (이러면 IOI 에서 마지막 I자리로 간다.)

또 현 위치에서부터 +2 위치까지 IOI를 찾는다. 이런식으로 카운팅한 개수가 n과 같다면 

answer 에 +1을 하고 

count를 - 1 해주는데 이유는 겹쳐져있는 IOI를 빠르게 구별하기 위함이다.

 

예를들어

n = 2라 하자

IOIOI 를 찾아야한다.

 

IOIOIOI 가 있다면 

i = 0 일 때 

IOI 찾고 카운팅 +1 위치는 i += 2로  2

i=2 일 때

IOI 찾고 카운팅 + 1 위치는 i += 2 로 4

if 문으로 카운팅 == 2 면 

answer + 1 

count - 1 

 

이때 -1 을 해주어서 카운팅 1일 때 찾은 IOI를 없애고 카운팅 2일때 IOI를 카운팅 1로 그 다음에 오는 IOI가 있으면 빠르게 겹쳐져있는 IOIOI를 찾을 수 있다. 

 

자세한건 코드를 머리속으로 돌려보면 이해가 된다. 

 

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    static boolean[] visited;
    static boolean[][] graph;
    static int max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        String line = br.readLine();
        int answer = 0;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            if (i + 2 >= m) {
                break;
            }

            if (line.charAt(i) == 'I' && line.charAt(i+1) == 'O' && line.charAt(i+2) == 'I') {
                count++;
                i++;

                // n만큼 있으면 anwer +1 하고 count -1을 해주어서 연속으로 또 찾을 기회를 준다. 
                if (count == n) {
                    answer++;
                    count--;
                }
                
            } else {
                count = 0;
            }
        }

        bw.write(answer + "");
        bw.flush();
        bw.close();
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  문자열 문제를 다시 좀 풀어야겠다.