[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 코드 풀이
코드 실행 결과
후기
처음에. substring() 함수로 해결하려 하였으나 시간 초과,
이후 String끼리. equals() 함수로 비교하였을 때 통과, 그러나 연산 시간 오래 걸림
이후 String형이 아닌. charAt() 함수 이용해 char형으로 비교하니 최적의 연산 시간 발견
문제 원본
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이 몇
www.acmicpc.net