[JAVA / 자바] 백준 5525번 - IOIOI (실버 2)

 문제 

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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

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

---

 입력 

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

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

---

 출력 

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

---

---

 문제 접근 방법 

이번 문제는 "I"+"OI" x N인 문자열(Pn)이 몇 개의 부분집합으로 존재하는지 물어보는 문제이다.

 

여기서 비교대상 문자열(Pn)은 입력되는 숫자에 의해 반복되는 길이가 달라지는데 주의해야 할 점은,

"IOI"가 반복되는 것이 아니라 "OI"가 반복된다는 점이다.

따라서, 입력 문자열 S에 Pn이 포함되어있는지 비교해줄 때, "OI"가 연속으로 n만큼 들어있는지를 먼저 확인하고 이후에 맨 앞에 "I"가 맞는지 확인해 카운팅 해주면 된다.

 

이때, 한 번에 비교하는 문자가 2자이므로, "OI"가 만약 일치해서 다음을 비교할 때에는 인덱스를 +2해 주고,

일치하지 않아서 다음을 비교해야 한다면 인덱스를 +1 해준다.

 

이때, Pn을 찾아서 카운팅 해줄 때는 부분집합이 서로 중복될 수 있으므로, n만큼 "OI"가 중복됐는지 체크하는 변수를 -1해 주고 다음을 비교했을 때,

Pn이 완성된다면 카운팅을 해주고

일치하지 않는다면 n만큼 "OI"가 중복됐는지 체크하는 변수를 0으로 초기화해주고 일치하지 않은 경우 처리한 후 다시 비교를 이어나가면 된다.

 

이렇게 입력 문자열 S의 순회가 끝나면 총 몇 개가 포함되어있는지 출력하면 된다.

---

 JAVA 코드 풀이 

	import java.io.*;
	public class Main {
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	int m = Integer.parseInt(br.readLine());
	String str = br.readLine();
	int cnt = 0, ans = 0;
	for(int i=1; i<m-1; ) {
	if(str.charAt(i) == 'O' && str.charAt(i+1) == 'I') {
	cnt++;
	if(cnt == n) {
	if(str.charAt(i-(cnt*2-1)) == 'I')
	ans++;
	cnt--;
	}
	i += 2;
	}
	else {
	cnt = 0;
	i++;
	}
	}
	System.out.println(ans);
	}
	}

view raw 5525.java hosted with ❤ by GitHub

 코드 실행 결과 

---

 후기 

처음에. substring() 함수로 해결하려 하였으나 시간 초과,

이후 String끼리. equals() 함수로 비교하였을 때 통과, 그러나 연산 시간 오래 걸림

이후 String형이 아닌. charAt() 함수 이용해 char형으로 비교하니 최적의 연산 시간 발견

---

 문제 원본 

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

5525번: IOIOI

 알고리즘 분류 

• 문자열