https://www.acmicpc.net/problem/5525
내 코드
(이 코드를 fread를 써서 수정하여 처음으로 1등을 했다 ㅎㅎ
하지만 아무도 읽어주지를 않는다 ㅠㅠ)
#include <stdio.h>
int main()
{
char S[1000001];
int i, x, N, M;
int n = 0;
int length = 0;
scanf("%d", &N);
scanf("%d", &M);
scanf("%s", S);
if (S[0] == 'I') length = 1; //I일 때부터 IOI가 반복되는 문자열의 길이를 +1 하고 싶었다.
for (i = 0; i < M - 1; i++)
{
if (S[i] == S[i + 1]) // 문자가 같은게 나오는 순간 IOIOI 식으로 반복되는게 멈춘 것이므로 이렇게 조건문을 달았다.
{
x = ((length - 1) / 2 - N + 1);
if (x > 0) n += x; // 이 부분이 핵심이다. 몫이 0인데 N이 1보다 크면 음수가 나올 수도 있는데 그런 경우는 0으로 취급하기 위해 이렇게 또 조건문을 썼다.
if (S[i + 1] == 'O') length = 0;
else length = 1; // 마찬가지로 I로 시작할 때부터 문자열의 길이를 1로 보고 싶기 때문
}
else
{
length++; //번갈아 나올 때마다 문자열의 길이를 더하기 1한다.
}
}
x = ((length - 1) / 2 - N + 1);
if (x > 0) n += x; // 마지막까지 문자열이 반복될 경우 n에 나올 수 있는 문자열의 개수가 더해지지 않으므로 이렇게 반복문이 끝난 후 한번더 연산을 넣어주었다.
printf("%d", n);
return 0;
}내 코드에서 조건문이 반복되는걸 볼 수 있는데
이 코드에서는
1. I로 시작할 때부터 문자열의 길이를 계산하기 위해
2. (IOIOI... 문자열의 길이 - 1) /2 - N + 1이 음수가 나올 수 있기 때문에 n에서 음수가 더해지는 걸 막기 위하여
조건문을 썼으나 조건문이 남용되면 실수가 나오기 쉬움을 알기에
조건문을 나보다 덜 쓴 코드를 보고자 한다.
또한 시간 역시 12ms 걸렸는데 나보다 짧은 코드를 보고 싶었다.
yukariko 님의 코드
https://www.acmicpc.net/source/358785
걸린 시간은 8ms
main()
{
int N,M;
char a[1000001];//널값을 받기 위해 100만1칸으로 설정
scanf("%d%d ",&N,&M);
gets(a);
//scanf에서 %d%d 뒤에 공백을 띄워줌으로서 엔터를 소비, 따라서 버퍼에 개행문자가 남지않아 문자열을 정상적으로 받아올 수 있다.
이전에 백준을 공부하면서 gets가 scanf보다 성능이 좋다는걸 알아서 여기서 시간차이가 난다는 것을 알 수 있었다.
그리고 친구를 통해
fread라는 함수를 배워 써보았더니 시간이 0ms가 되었다.
직접 접근하는 함수라서 빠르다는데 원리를 이해하려면 시스템 프로그래밍을 배워야한다고 한다.
fread 사용법 : (저장할 문자열의 주소, 문자열 사이즈, 반복 횟수, 읽을 파일 포인터)
원리 : 파일 포인터를 stdin으로 입력하면 문자열 사이즈만큼 버퍼에서 문자를 가져와서 적어놓은 메모리 주소에 저장한다.
int i,count=0,res=0;
for(i=0;i<M;i++)
{
if(count == 0)
{
if(strncmp(&a[i],"IOI",3) == 0){i+=2;count++;}
//strncmp는 길이를 가지고 비교하는 함수
strcmp와 비슷하지만 strcmp와 다르게
strncmp(문자열1,문자열2,비교할 길이)로 사용,
동일하면 0을 리턴하고 동일하지 않으면 1을 리턴한다.
}
//즉, 문자열 IOI가 발견되면 그 뒤로 i를 2더라고 또 같으면 count를 1 더한다. 여기서 count 는 내 코드의 n과 같은 역할.
else
{
if(a[i]=='O' && a[i+1] == 'I'){i++;count++;}
//IOIOIOIOOO를 예시로 들자. 처음에는 카운트가 0 세번째 칸으로 가서 count가 1 이 떄는 count가 0이 아니므로 else문으로 온다. 이 때 그전에 if문애서 i가 2더해지고 for문에 의해 i가 +1 되므로 i는 총 더라기 3, 이 때 a[ㅑ]는 'O'이므로 여기로 온다. 그리고 count눈 2, i는 이후 for문까지 거치면서 더하기 2
else {i--;count=0;}
//
예시로 보던걸 계속 보면 이후 O를 만났을 때 뒤가 I가 아니면 반복이 안되므로 i는 count를 이 칸부터 그대로 다시 검사하기 위해 i-- count는 초기화,
I를 만나면 당연히 반복이 안되므로 마찬가지.
이 칸부터 다시 해야하는 이유는 IOIOIIOI이면 여섯번째 칸이 I지만 여기서부터 count++해야하기 떄문
}
if(count >= N) res++;// 수학적으로 좋은 방법, 하지만 연산이 두배로 늘어나므로 연산량은 내 방법이 적다.
}
printf("%d",res);
}내 코드를 설명하면서 나도 내 코드를 확실하게 설명할 수 있도록 더 확실하게 알고리즘을 짜고 코드를 한줄한줄 이해해가며 짜야겠다는 생각을 했다.
fread는 종종 애용해야겠다 ㅎㅎ
