글 읽기 - [C99] 반례 찾아주시면 감사하겠습니다.

kms1212 1년 전 0

1. 각각의 입력받은 문자열들을 길이 순서로 배열합니다.

2. 그 문자열들을 역순으로 탐색하고 배열의 요소가 NULL이면 다음 요소로 건너뜁니다.

3. 2의 내부 루프에서 배열의 정방향 순서로 문자열이 접두어에 해당하는지 확인한 다음 포함되는 문자열이 있으면 모두 NULL처리한 뒤 결과값을 0에서부터 1씩 증가시킵니다.

문제의 예시들에서는 모두 정확한 결과값이 도출되었으며, 임의로 넣어본 결과값에서도 모두 정확하게 계산되었습니다. 아래는 테스트해본 입력과 그 출력입니다.

입력	출력	집합 (단, "(a \| b)"는 a 또는 b이며 출력에서는 a가 표시된다)
7 ca cade caed cae coff c cb	4	{cade, (caed \| cae), coff, cb}
8 cirt c criow vimnb bbm bbmiis vim aosi	5	{cirt, criow, (vimnb \| vim), (bbmiis \| bbm), aosi}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

void orderlistaslength(char** list, int cnt) {
    char** tmp = (char**)malloc(sizeof(char*) * cnt);
    memcpy(tmp, list, sizeof(char*) * cnt);
    char** tmp2 = (char**)malloc(sizeof(char*) * cnt);
    memcpy(tmp2, list, sizeof(char*) * cnt);

    int index = 0;
    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < cnt; j++) {
            if (tmp2[j][i] == 0 && tmp[j] != NULL) {
                list[index] = tmp[j];
                tmp[j] = NULL;
                index++;
            }
        }
    }
    free(tmp);
    free(tmp2);
}

int main(int argc, char** argv) {
    int wordcount;
    scanf("%d", &wordcount);

    int result = 0;

    char** wordlist = (char**)malloc(sizeof(char*) * wordcount);
    for (int i = 0; i < wordcount; i++) {
        wordlist[i] = (char*)malloc(sizeof(char) * 51);
        scanf("%s", wordlist[i]);
    }

    orderlistaslength(wordlist, wordcount);
    for (int i = wordcount - 1; i >= 0; i--) {
        //printf("Current word: %s\n", wordlist[i]);

        if (wordlist[i] == NULL)
            continue;

        for (int j = 0; j < i; j++) {
            int tmp = 0;
            if (wordlist[j] == NULL)
                continue;
            for (int k = 0; k < strlen(wordlist[i]); k++)
                if (wordlist[i][k] == wordlist[j][k])
                    tmp++;
            if (tmp == strlen(wordlist[j])) {
                //printf("%s contains %s\n", wordlist[i], wordlist[j]);
                wordlist[j] = NULL;
            }
        }
        result++;
        wordlist[i] = NULL;
        //printf("Result value: %d\n", result);
    }

    for (int i = 0; i < wordcount; i++)
        free(wordlist[i]);
    free(wordlist);

    printf("%d\n", result);
}

chldnjstjrttt 1년 전 1

반례입니다 힌트는 orderlistaslength 함수에서 한글자만 바꾸면 됩니다 문자열 마지막에 NULL들어가는거를 고려해서.......

7
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaae
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaa
aaaa

kms1212 1년 전 0

orderlistaslength 함수에서 i를 반복자로 하는 for문의 범위를 1 증가시켜서 제시해주신 반례의 결과값이 4에서 5로 바뀌었습니다. 그런데...

코드를 다시 제출해보니까 또 틀렸습니다로 나오네요...

어떤 다른 문제점이 있을까요?

chldnjstjrttt 1년 전 0

저도 13번째줄에서 50을 51로 바꾸니까 제꺼는 정답 떠요

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

void orderlistaslength(char** list, int cnt) {
    char** tmp = (char**)malloc(sizeof(char*) * cnt);
    memcpy(tmp, list, sizeof(char*) * cnt);
    char** tmp2 = (char**)malloc(sizeof(char*) * cnt);
    memcpy(tmp2, list, sizeof(char*) * cnt);

    int index = 0;
    for (int i = 0; i < 51; i++) {
        for (int j = 0; j < cnt; j++) {
            if (tmp2[j][i] == 0 && tmp[j] != NULL) {
                list[index] = tmp[j];
                tmp[j] = NULL;
                index++;
            }
        }
    }
    free(tmp);
    free(tmp2);
}

int main(int argc, char** argv) {
    int wordcount;
    scanf("%d", &wordcount);

    int result = 0;

    char** wordlist = (char**)malloc(sizeof(char*) * wordcount);
    for (int i = 0; i < wordcount; i++) {
        wordlist[i] = (char*)malloc(sizeof(char) * 51);
        scanf("%s", wordlist[i]);
    }

    orderlistaslength(wordlist, wordcount);
    for (int i = wordcount - 1; i >= 0; i--) {
        //printf("Current word: %s\n", wordlist[i]);

        if (wordlist[i] == NULL)
            continue;

        for (int j = 0; j < i; j++) {
            int tmp = 0;
            if (wordlist[j] == NULL)
                continue;
            for (int k = 0; k < strlen(wordlist[i]); k++)
                if (wordlist[i][k] == wordlist[j][k])
                    tmp++;
            if (tmp == strlen(wordlist[j])) {
                //printf("%s contains %s\n", wordlist[i], wordlist[j]);
                wordlist[j] = NULL;
            }
        }
        result++;
        wordlist[i] = NULL;
        //printf("Result value: %d\n", result);
    }

    for (int i = 0; i < wordcount; i++)
        free(wordlist[i]);
    free(wordlist);

    printf("%d\n", result);
}

kms1212 1년 전 0

어...? 이제는 또 성공이네요.. 다른 실수가 있었던 건가 봐요 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C99] 반례 찾아주시면 감사하겠습니다.

kms1212 1년 전 0

chldnjstjrttt 1년 전 1

kms1212 1년 전 0

chldnjstjrttt 1년 전 0

kms1212 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말