[백준] 5525번: IOIOI_JAVA

문제 (https://www.acmicpc.net/problem/5525)

문제

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로만 이루어져 있다.

 

서브태스크

 

번호배점제한

1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

 

예제 입력 1

1
13
OOIOIOIOIIOII

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 출력 1 

4

 

예제 입력 2

2
13
OOIOIOIOIIOII

• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 출력 2

2

풀이

- 어떤 Pn의 개수를 찾을 것인지 N(n),  S(IOIOIOIOOI 등), S의 길이 M을 입력 받는다.

 

- OI가 반복되는 것에 주목

 

- OI 단위로 한번에 확인하다가 N의 개수에 일치하면 앞쪽이 I인지 O인지를 확인하는 방식으로 반복

 

- OI의 시작 부분의 앞 부분이 I인지 O인지를 확인하려면 OI 단위로 확인하다가 N의 개수가 일치하게 되는 지점

에서 2N - 1 만큼 앞의 문자가 I인지 O인지 확인하면 된다. 

(N = 2일 때, IOIOI 밑줄 친 인덱스 부분(i)에서 i - (2 * N - 1)를 해준 인덱스의 문자를 확인하면 된다) 

(N에 따라 1, 3, 5, 7 ' ' ' (2 * N -1) 등차수열 규칙을 가짐)

 

- I이면 Pn 의 개수를 + 1, O이면 OOI 이므로 맨 앞 OI는 Pn 규칙에 부적합하므로 배제한다.

 

- 반복문으로 위 과정을 반복한다.  

 

---

코드

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt(); //N(n)의 크기 (Pn) 
		int M = scan.nextInt(); //S의 길이 M
		String str = scan.next(); //OOIOIOIOIIOII 같이 문자열이 들어갈 변수 str
		int result = 0; //Pn의 개수
		int cnt = 0; //Pn이 일치하는 지 확인하기 위해 OI의 개수를 저장하는 정수형 변수
		
		for (int i = 1; i < M - 1; i++) {
       		 //OI가 반복되는 거를 중심으로 체크
			if (str.charAt(i) == 'O' && str.charAt(i + 1) == 'I') { 
				cnt++;
				if(cnt == N) {
					if(str.charAt(i - (2 * N - 1)) == 'I') { //앞에 I인지 o인지 확인
						result++;
					}
                     //앞이 O인 경우 OOI 이므로 제거, 앞이 I이더라도 다음 OI가 나올 수도 있기 때문에
					cnt--;
				}
				i++; // OI이므로 OI 단위로 체크하기 위해  한칸 더 건너 뛰기
			}
			else {
				cnt = 0; // OI가 반복되지 않을 경우 다시 0으로 초기화
			}
		}

		System.out.println(result); //결과 출력
		scan.close();
	}