[백준] 5525 - IOIOI JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

https://www.acmicpc.net/problem/5525

5525번: IOIOI

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

P1 IOI
P2 IOIOI
P3 IOIOIOI
PN IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력
S에 PN이 몇 군데 포함되어 있는지 출력한다.

제한
1 ≤ N ≤ 1,000,000
2N+1 ≤ M ≤ 1,000,000
S는 I와 O로만 이루어져 있다.

접근방법

 해당 문자열이 Pn의 형태를 얼마나 가지고 있는지, 갯수를 반환하는 문제이다.

풀이

  모든 Pn은 'I'로 시작한다. 또한 P1은 'I'와 'I' 사이의 인덱스 차이가 2임을 이용한다.  문자열에 'I'가 있는 인덱스를 저장하고, 각 인덱스의 차이를 이용한다. P의 규칙성은 'I' 와 'I' 사이의 간격이 2차이 나므로, 해당 차이가 날 때마다 카운트를 올리고, 차이가 N인 구간에서 결과값을 증가시켜주면된다.   

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int len = Integer.parseInt(br.readLine());
        String str = br.readLine();
        List<Integer> start = new ArrayList<>();

        for (int i = 0 ; i < str.length()-1;i++){
            if( str.charAt(i) =='I'){
                start.add(i);
            }
        }

        int cnt=0,result=0 ;
        for (int i = 1 ; i < start.size() ; i++){
            if(start.get(i) - start.get(i-1) == 2){
                cnt++;
            }else{
                cnt =0;
            }

            if( cnt>= N){
                result++;
            }


        }

        System.out.println(result);



    }
}

결과

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.