[백준/Java] 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로만 이루어져 있다.

 
 

- 문제 풀이 방법

- 풀이1

1) 문자가 I인 경우 
   - 해당 문자부터 2N개의 문자를 확인한다.
   - I, O가 번갈아서 나오는지 확인한다. 
    같은 문자가 아니면 cnt++
2) cnt값이 2N과 같다면 answer++
 
=> 50점이 나온다. 50점이 나오는 건 입력값이 작을 땐 정답이지만 클 땐 시간초과가 나와서라고 한다. 
 
 

- 풀이2

P1은 IOI, P2는 IOIOI ...로 가운데 값을 기준으로 대칭이다.  
풀이 1과 동일하되 문자가 I인 경우 해당 문자부터 2N개의 문자를 확인하는데
1) 중간값을 먼저 보고 n이 홀수인 경우(P1 = IOI) 가운데 값은 O이고 짝수인 경우(P2 = IOIOI) 가운데 값은 I인 걸 먼저 확인해주었다. 

if (n % 2 == 1 && s[i+n] != 'O') {
	continue;
}
if (n % 2 == 0 && s[i+n] != 'I') {
	continue;
}

2) 이후 중간값 제외하고 대칭인지 체크한다. 

=> 정답x
 
 

- 풀이3

1) 문자가 I인 경우 해당 인덱스를 배열에 따로 저장한다. 
   IOIOI -> [0,2,4] 
2) n이 1일 때 iArr[i]과 iArr[i+n]의 차이가 2(n*2)이면 answer++ 해준다.
    -> 0과 2의 차이가 2, 2와 4의 차이가 2
 
    n이 2일 때는 iArr[i]과 iArr[i+n]의 차이가 4(n*2)이면 answer++ 해준다.
    -> 0과 4의 차이가 4
 
 

- 코드

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.nextLine());
		int m = Integer.parseInt(sc.nextLine());
		char[] s = sc.nextLine().toCharArray();
		
		int[] iArr = new int[m];
		int idx = 0;
		
		int answer = 0;
		int cnt = 0;
		
		//I인 경우 배열에 i의 인덱스 추가
		for (int i = 0; i < m; i++) {
			if (s[i]=='I') {
				iArr[idx++] = i;
			}
		}
		
		for (int i = 1; i < idx; ++i) {
			if(iArr[i]-iArr[i-1] == 2) {
				cnt++;
			}else {
				cnt = 0;
			}
			if(cnt >= n) {
				answer++;
			}
		}
		
		System.out.println(answer);
		
		sc.close();
	}

}

 


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

5525번: IOIOI