2009 정보올림피아드 지역본선 문제 Review (1)

현재 난 고2다. 고로 난 고등부 정올에 나갔다(-_-;)
중딩 때부터 나갔으면 전국본선을 노릴 만하다고 생각하지만...
올해가 고작 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
17772345
22233331

출력 (OUTPUT.TXT)

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;