중딩 때부터 나갔으면 전국본선을 노릴 만하다고 생각하지만...
올해가 고작 2년째라서 상당히 병맛이다. 결과는 6월 5일에 나온다는군.
잡설은 집어치우고 각설.
연속구간ㅋㅋ 난 이래서 티스토리가 좋아 ㅋㅋㅋㅋㅋ
여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 작성하라.
예를 들어 세 개의 숫자 12345123, 17772345, 22233331이 주어졌다고 하자. 12345123은 연속하여 같은 숫자가 나오는 것이 없으므로 1을 출력하고, 17772345는 7이 세 개 연속하여 나오므로 3을 출력하며, 22233331의 경우에는 2가 세 개, 3이 네 개 연속해서 나오므로 그 중 큰 값인 4를 출력하여야 한다.
실행파일의 이름은 CONT.EXE로 하고 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
입력 형식
입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄부터 셋째 줄까지 각 줄에 하나씩 세 개의 여덟 자리 양의 정수가 주어진다.
출력 형식
출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에서 셋째 줄까지 한 줄에 하나씩 각 입력된 수 내에서 같은 숫자가 연속하여 나오는 가장 긴 길이를 입력 순서대로 출력한다.
입력과 출력의 예
입력 (INPUT.TXT)
12345123출력 (OUTPUT.TXT)
17772345
22233331
1
3
4
일단 이 문제는 상당히 단순하다.
입력은 8자리 자연수 3개뿐이다. 앞에 자료의 수가 나오고 어쩌고 없다.
그러면 일단 파일을 열고 3개의 정수를 입력받아 보자.
#include <stdio.h> int main() { FILE *fp; int a, b, c; fp = fopen("INPUT.TXT", "r"); fscanf(fp, "%d %d %d", &a, &b, &c); /* 이제 a, b, c를 가지고 장난을 치겠지. * ............ */ return 0; }-_-;
미쳤냐.
실제로 써야 하는 데이터는 수가 아니라 숫자일세..
숫자를 써야 하는데 뭐하러 수로 입력받아서 다시 자릿수로 나누고 ㅈㄹ(-_-;)을 하세요.
그러므로 그냥 내용을 입력받을 때 8자리 문자열 배열로 입력받으면 된다.
#include <stdio.h> int main() { FILE *fp; char a[9], b[9], c[9]; // 왜 9개인지는 알지ㅡ_ㅡ fp = fopen("INPUT.TXT", "r"); fscanf(fp, "%s %s %s", a, b, c); /* 이제 a, b, c를 가지고 장난을 치겠지. * ............ */ return 0; }이렇게.
그런데 생각해 보면 실제로 정올 문제 중 배열에 저장하지 않고 풀 수 있는 문제가 있다.
역대 1번 문제들이 그랬다. -_-;
특히 9*9 배열 중 최댓값을 찾는 문제는....
배열 만들어서 모조리 저장하고 다시 처음부터 찾고 하는 방식을 쓰면
두 배의 시간이 걸린다. 병맛이지.
이 문제도 마찬가지. 처음부터 다시 짜 보자.
일단 8자리 문자열(.....)이 세 개 주어지며, 따로 처리하게 되어 있으므로,
{하나 처리하고 하나 출력하고}를 세 번 반복하자.
그럼 파일 포인터가 두 개 필요하고, 세 번 루프를 돌아야 한다.
#include <stdio.h> int main() { FILE *fpi, *fpo; int i, j, conti; char str[8]; fpi = fopen("INPUT.TXT", "r"); fpo = fpoen("OUTPUT.TXT", "w"); for (i = 0; i < 3; i++) { fscanf(fpi, "%s", str); /* 이제 j를 사용해 str에서 가장 큰 반복 횟수를 conti에 저장할 거다. */ fprintf(fpo, "%d\n", conti); } return 0; }-_-;
나아진 게 없잖아.
보기에만 좋아졌지 배열에 저장한 후에 처리하는 건 달라지지 않았다.
(아니, 메모리는 덜 쓴다. 실제로 많은 다중데이터 문제에서 이래야만 한다.)
그래서 루프를 한 번 더 돌린다-_-;
흐르듯이 처리하려면 이전 문자랑 비교해야 하니까 문자 변수를 두 개 두자.
하나는 입력, 하나는 비교용.
#include <stdio.h> int main() { FILE *fpi, *fpo; int i, j, conti; char n, c; fpi = fopen("INPUT.TXT", "r"); fpo = fopen("OUTPUT.TXT", "w"); for (i = 0; i < 3; i++) { conti = 1; for (j = 0; j < 8; j++) { fscanf(fpi, "%c", &n); /* n이 이전 글자와 같으면 conti++, 다르면 conti = 1 */ } fprintf(fpo, "%d\n", conti); // 반복 횟수 쓰고 한 줄 내리고. } return 0; }미친 게 틀림없다.
......
뭐 어때.
구조적인 프로그래밍 갖다 버리고 속도만 유지하고 싶은가.
문자로 받아서 7번 비교하고 결과 출력하는 작업을 코드에 똑같이 세 개 넣으면 된다.
그건 좀 아니잖아-_-;
어쨌든 이제 진짜 중요한, 주석으로 처리한 부분을 연구해 보자.
일단 '이전 문자'와 비교해야 한다.
그런데 처음 시작, 인덱스 0일 때 문제가 생긴다.
이전 문자가 누구세요...-_-;;;
그래서 사실 j에 관한 for문 아래에 if문을 둬서
j가 0일 때에는 묻지도 따지지도 않고 conti = 1, c = n으로 퍼 줘야 하겠다.
근데 저 j에 관한 for문은 알짜로 24번 실행된다.
시간 낭비가 생길 위험이 있으므로 일단 하나를 for문 밖에서 입력받고,
j는 1부터 시작하자. 미안.
#include <stdio.h> int main() { FILE *fpi, *fpo; int i, j, conti; char n, c; fpi = fopen("INPUT.TXT", "r"); fpo = fopen("OUTPUT.TXT", "w"); for (i = 0; i < 3; i++) { conti = 1; fscanf(fpi, "%c", &c); for (j = 1; j < 8; j++) { fscanf(fpi, "%c", &n); if (n == c) //위에서 주석문으로 처리한 부분을 구현한다. conti++; else { conti = 1; c = n; } } if (i != 0) fprintf(fpo, "\n"); /* 출력 형식을 제대로 맞춘다. */ fprintf(fpo, "%d", conti); } return 0; }
잘~ 실행된다.
꺼져ㅋㅋㅋㅋㅋㅋ 잘 실행되기는 무슨 ㅋㅋㅋ
문제가 뭘까요-_-;
이 코드의 문제점은 conti가 계속 갱신된다는 점에 있다.
최대 conti가 저장되지 않는다.....
그리하여 정말 정상적인 코드...
#include <stdio.h> int main() { FILE *fpi, *fpo; int i, j, conti, max; char n, c; fpi = fopen("INPUT.TXT", "r"); fpo = fopen("OUTPUT.TXT", "w"); for (i = 0; i < 3; i++) { max = 1; conti = 1; fscanf(fpi, "%c", &c); for (j = 1; j < 8; j++) { fscanf(fpi, "%c", &n); if (n == c) conti++; if (max < conti) max = conti; if (n != c) { conti = 1; c = n; } } if (i != 0) fprintf(fpo, "\n"); fprintf(fpo, "%d", max); } return 0; }...라고 생각했으나 작동 결과가 영 병맛인 코드.
결론부터 말하자면, fscanf를 디버그 모드에서 돌려 보자,
%c 자리에 이쁘게 10을 넣어 주시더라. ASCII 10이 뭐게요.
쉣. 읽을 공백은 안 읽고 웬 줄바꿈은 읽고...
시험장에서 같은 문제에 걸려서 대충 루프 내 if문 조정하면서 해결했다.
그러나 제대로 된 해법은 그냥 한 번 더 입력받기.
#include <stdio.h> int main() { FILE *fpi, *fpo; int i, j, conti, max; char n, c; fpi = fopen("INPUT.TXT", "r"); fpo = fopen("OUTPUT.TXT", "w"); for (i = 0; i < 3; i++) { max = 1; conti = 1; fscanf(fpi, "%c", &c); for (j = 1; j < 8; j++) { fscanf(fpi, "%c", &n); if (n != c) { conti = 1; c = n; continue; } // 이걸 먼저 처리해서 continue로 보내 버리면 좀 더 빠르다. conti++; if (max < conti) max = conti; } fprintf(fpo, "%d", max); if (i < 3) { fprintf(fpo, "\n"); fscanf(fpi, "%c", &c); } } fclose(fpi); fclose(fpo); // 파일 포인터 닫는 것도 잊지 말고. return 0; }인정한다. 모범답안은 이것보다 빠를 거다...-_-;
그냥 바로 적당한 코드 해설했어야 하는데 잡소리가 너무 길었습니다.
글이 길어진 점 사과드립니다 0_0;
'Sablog Models > 알고리즘' 카테고리의 다른 글
2009 정보올림피아드 지역본선 문제 Review (3)-1 (3) | 2009.07.18 |
---|---|
2009 정보올림피아드 지역본선 문제 Review (2)-3 (6) | 2009.07.18 |
2009 정보올림피아드 지역본선 문제 Review (2)-2 (0) | 2009.06.21 |
2009 정보올림피아드 지역본선 문제 Review (2)-1 (0) | 2009.06.14 |
2009 정보올림피아드 지역본선 문제 Review (1) (9) | 2009.06.02 |
Programming: Problem-Solving Process. (3) | 2009.05.03 |