[백준] 알고리즘 분류(문자열,JAVA)5525번, IOIOI

문제 링크

5525번: IOIOI

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. n의 값에 따라 'IOI'의 형태 문자열이 만들어집니다.

2. 문자열 S에 Pn에 포함되는 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 문자열 S를 탐색하여 Pn에 해당하는 문자열이 몇 개 포함되는지 탐색합니다.

 

3. 포함된 개수를 결과로 출력합니다.

 

 

문자열 탐색

 

Pn의  문자열 형태

 

P₁  = "IOI" : 문자열 길이 3

P₂  = "IOIOI" : 문자열 길이 5

P₃  = "IOIOIOI" : 문자열 길이 7

P₄  = "IOIOIOIOI" : 문자열 길이 9

.....

Pn = "I" + "OI" × n

문자열 길이 : (2 × n) + 1

 

문자열 탐색

 

문자열 : "IOIOI" (P₂)

 

P₁ = 2개("IOIOI", "IOIOI")

P₂  = 1개("IOIOI")

 

문자열 : "IOIOIOI"(P₃)

 

P₁ = 3개("IOIOIOI", "IOIOIOI", "IOIOIOI")

P₂ = 2개("IOIOIOI", "IOIOIOI")

P₃ = 1개("IOIOIOI")

 

Pn의 문자열일 때

 

P₁ : n - (1 - 1) = n

P₂ : n - (2 - 1) = n-1

P₃ : n - (3 - 1) = n-2

....

Pn : n - (n - 1) = 1

 

 

S의 문자열을 탐색하다가 "IOI..."의 형태를 찾았을 경우 Pn이 몇 개 포함되는지 확인합니다.

 

예제입력 진행되는 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 1

M : 13

문자열 : OOIOIOIOIIOII

 

2. 문자열 S를 탐색하여 Pn에 해당하는 문자열이 몇 개 포함되는지 탐색합니다.

문자열 S를 탐색

 

OOIOIOIOIIOII

 

P₃ : IOIOIOI

 

P₁ 포함 개수 : 3 - (1 - 1) = 3개

 

OOIOIOIOIIOII

 

P1 : IOI

 

P₁ 포함 개수 : 1 - (1 - 1) = 1개

 

3. 포함된 개수를 결과로 출력합니다.

 

P₃ : IOIOIOI : 3개

P1 : IOI : 1개

 

4를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 문자열 S를 탐색하여 IOI..형태의 단어를 탐색합니다.
• IOI.. 단어의 형태가 종료되었을 때 Pn이 포함되는 개수를 cal함수를 통해서 구합니다.
• 문자열 S를 모두 탐색하였을 때 Pn이 포함되는 총 개수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 IOI.. 형태에서 Pn이 몇 개 포함되는지 계산합니다.

 

결과코드

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        String str = br.readLine();
        //pSize : Pn의 문자열 개수
        int pSize = 2*N + 1, answer = 0, count = 0;
        char cur = ' ';	//현재 문자
        //문자열 S 탐색
        for(int i=0;i<M;i++) {
            char c = str.charAt(i);
            //이전 문자와 다를 때
            if(cur != c) {
                //P형태의 문자열 시작!
                if(count == 0) {
                    if(c =='I') {
                        count++;
                        cur = c;
                    }
                }else {		//문자열 증가
                    cur = c;
                    count++;
                }
            }else {
                //IOI형태 종료, 지금까지 만들어진 IOI... 문자열 Pn 포함 개수 구하기
                answer += cal(pSize, count, N);
                count = 0;
                //P형태의 문자열 시작!
                if(c == 'I')
                    count++;
                cur = c;
            }
        }
        //마지막 저장된 IOI..형태에서 Pn포함 개수 구하기
        answer += cal(pSize, count, N);
        bw.write(answer + "");	//Pn 총 포함 개수 BufferedWriter
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //IOI...형태에서 Pn포함 개수 구하는 함수
    static int cal(int size, int count, int N) {
        int result = 0;
        if(count >= size) {
            int temp = (count - 1)/2;		//IOI..형태에서 N구하기
            result = temp - (N-1);		//포함 개수 구하기
        }
        return result;	//포함 개수 반환
    }
}