Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- 항해99
- 개발자취업
- 브루트포스
- 프로그래머스
- 우선순위큐
- 백트래킹
- 네트워크 계층
- 정렬
- 자바
- Til
- lower bound
- BFS
- 99클럽
- 동적 프로그래밍
- 그래프 이론
- 데이터베이스
- 코딩테스트준비
- 그래프
- 트리
- Spring
- 완전탐색
- Java
- 스프링 핵심 원리 - 기본편
- 백준
- BinarySearch
- DP
- 스프링
- 그리디
- DFS
- 알고리즘
Archives
- Today
- Total
AtraFelis's Develop Diary
[백준] 5525 - IOIOI (C언어) 본문
백준 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에 $P_N$이 몇 군데 포함되어 있는지 출력한다.
제한
- $1 ≤ N ≤ 1,000,000$
- $2N+1 ≤ M ≤ 1,000,000$
- S는
I
와O
로만 이루어져 있다.
서브태스크
번호 | 배점 | 제한 |
---|---|---|
1 | 50 | N ≤ 100, M ≤ 10 000. |
2 | 50 | 추가적인 제약 조건이 없다. |
풀이
시도 1
모든 문자열에 대해서 I가 나올 때마다, 뒷문자열을 확인하여 $P_n$ 이 등장하는지 확인해주었다.
만약, n = 2 라면 IOIOI가 등장하는지만 확인하면 된다.
bool find = true;
int answer = 0;
for (int i = 0; i < m; i++) {
find = true;
if(str[i] == 'I'){
for (int k = 1; k < 2*n+1; k+=2) {
if(!(str[i+k] == 'O' && str[i+k+1]=='I')){
find = false;
break;
}
}
if(find) answer++;
}
}
서브태스크 1에서는 최대 100 * 10000
회 반복이므로 통과가 되지만, 서브태스크 2에서는 최대 1,000,000*1,000,000
반복이 되어 주어진 시간 내에 성공하지 못한다.
즉, 통과하려면 시간복잡도를 효율적으로 바꾸어야 한다.
시도 2
int answer = 0;
for (int i = 0; i < m; i++) {
if(str[i] == 'I'){
int p = 0;
for (int k = 1; ; k+=2) {
if(!(str[i+k]=='O' && str[i+k+1]=='I')){
i += k-1;
break;
}
p++;
}
if(p >= n)
// 조건 없으면 p-n+1이 음수가 되어버리는 경우가 발생함.
answer += p-n+1;
}
}
반복 횟수를 줄이기 위해서, I가 등장하면 $P_n$가 만족할 때까지 검사한후, 찾아낸 P 문자열 안에 $P_n$이 몇 개 있는지 확인했다.
$P_N$ 안의 $P_k$는 $N-k+1$ 개가 존재한다. (N <= K)
이렇게 하면, $O(M)$ 정도의 시간복잡도로 답을 구해낼 수 있다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int main() {
int n, m;
scanf("%d %d", &n, &m);
char *str = (char*)malloc(sizeof(char)*m);
scanf("%s", str);
int cnt = 0;
int answer = 0;
for (int i = 0; i < m; i++) {
cnt++;
if(str[i] == 'I'){
int p = 0;
for (int k = 1; ; k+=2) {
cnt++;
if(!(str[i+k]=='O' && str[i+k+1]=='I')){
i += k-1;
break;
}
p++;
}
if(p >= n) // 조건 없으면 p-n+1이 음수가 되어버리는 경우가 발생함.
answer += p-n+1;
}
}
printf("%d", cnt);
free(str);
return 0;
}
'Algorithm > 백준' 카테고리의 다른 글
[백준] 1005 - ACM Craft (JAVA) (0) | 2024.06.24 |
---|---|
[백준] 12865 - 평범한 배낭 (JAVA) (0) | 2024.05.21 |
[백준] 16953 - A → B (JAVA) (0) | 2024.05.14 |
[백준] 11725 - 트리의 부모 찾기 (JAVA) (0) | 2024.05.05 |
[백준] 20529 - 가장 가까운 세 사람의 심리적 거리 (C언어) (0) | 2024.04.16 |