편집 기록

프로필 편집요청빌런님의 편집

날짜2020.02.11

백준 알고리즘 질문

algorithm

c

일단 문제 링크는

: https://www.acmicpc.net/problem/2941

이겁니다.

배열을 이용해서 풀었는데 우선 첫번째로 푼 코드는 아래와 같습니다.

/*

                                <1>

*/

#include <stdio.h>

#include <string.h>

#include <stdbool.h>



#define MAX_COUNT 8

#define MAX_LENGTH 4

#define MAX_FIND_LENGTH 101



int COUNT_CHAR(char temp[], char(*words)[MAX_LENGTH], int len, int size);



int main() {


    int len = 0;

    char words[MAX_COUNT][MAX_LENGTH] = {
                {"c="},

                {"c-"},

                {"dz="},

                {"d-"},

                {"lj"},

                {"nj"},

                {"s="},

                {"z="}

    };

    char temp[MAX_FIND_LENGTH];



    scanf(temp);

    len = strlen(temp);



    printf("%d\n", COUNT_CHAR(temp, words, len, MAX_COUNT));



    return 0;



}



int COUNT_CHAR(char temp[], char(*words)[MAX_LENGTH], int len, int size) {


    int index = 0, temp_index = 0;

    int total_count = 0;

    int now_count = 0;

    bool flag = false;



    for (int i = 0; i < len; i++) {


        if (flag)

            total_count++;

        flag = true;

        index = 0;

        for (int j = 0; j < size; j++) {


            if (temp[i] == words[j][0]) {


                temp_index = i;



                while (words[j][index] && temp[temp_index]) {


                    if (words[j][index] != temp[temp_index]) {


                        index = 0;

                        break;

                    }

                    index++;

                    temp_index++;

                }

                if (words[j][index] == 0) {




                    flag = false;

                    i = temp_index - 1;

                    total_count++;

                    break;

                }

            }

        }



    }

    if (flag)

        total_count++;



    return total_count;

}

위 코드로 채점을 해봤을때 시간 초과가 나와서 안됬고 딱히 아이디어가 생각 나지 않아서

다음날 다시 짜본 코드는 아래와 같습니다.

/*

                                <1>

*/

#include <stdio.h>

#include <string.h>

#include <stdbool.h>



#define MAX_COUNT 8

#define MAX_LENGTH 4

#define TEMP_LENGTH 101



int main() {


    char words[MAX_COUNT][MAX_LENGTH] = {
        {"c="},

    {"c-"},

    {"dz="},

    {"d-"},

    {"lj"},

    {"nj"},

    {"s="},

    {"z="}

    };



    char temp[TEMP_LENGTH];

    int total_count = 0;

    int len, index = 0;

    int temp_index = 0;

    bool flag;



    scanf(temp);

    len = strlen(temp);



    for (int i = 0; i < len; i++) {


        temp_index = i;

        for (int j = 0; j < MAX_COUNT; j++) {
            flag = false;



            if (temp[temp_index] == words[j][0]) {


                while (words[j][index]) {


                    if (temp[temp_index] != words[j][index]) {


                        temp_index = i;

                        index = 0;

                        break;

                    }

                    index++;

                    temp_index++;

                }

                if (words[j][index] == 0) {
                    flag = true;

                    total_count++;

                    i = temp_index - 1;

                    index = 0;

                    break;

                }

                if (!flag && (j == MAX_COUNT - 1)) {
                    total_count++;

                }

            }

            if (!flag && (j == MAX_COUNT - 1)) {
                total_count++;



            }

        }

    }



    printf("%d\n", total_count);



    return 0;   

}

두번째로 짠 코드도 제 컴파일러에서는 제대로 작동되지만 이번에는 시간 초과가 아닌 잘못된 풀이라고 하네요... 어디를 수정하고 어디를 고쳐야 할까요? 이틀정도 들여다 봤는데 이제더이상 아이디어가 안떠오릅니다 ㅠ

프로필 알 수 없는 사용자님의 편집

날짜2020.02.11

백준 알고리즘 질문

algorithm

c

일단 문제 링크는

: https://www.acmicpc.net/problem/2941

이겁니다.

배열을 이용해서 풀었는데 우선 첫번째로 푼 코드는 아래와 같습니다.

<1>

include

define MAX_COUNT 8

define MAX_LENGTH 4

define MAX_FIND_LENGTH 101

int COUNT_CHAR(char temp[], char(*words)[MAX_LENGTH], int len, int size);

int main() {

int len = 0;

char words[MAX_COUNT][MAX_LENGTH] = {
            {"c="},

            {"c-"},

            {"dz="},

            {"d-"},

            {"lj"},

            {"nj"},

            {"s="},

            {"z="}

};

char temp[MAX_FIND_LENGTH];



scanf(temp);

len = strlen(temp);



printf("%d\n", COUNT_CHAR(temp, words, len, MAX_COUNT));



return 0;

}

int COUNT_CHAR(char temp[], char(*words)[MAX_LENGTH], int len, int size) {

int index = 0, temp_index = 0;

int total_count = 0;

int now_count = 0;

bool flag = false;



for (int i = 0; i < len; i++) {


    if (flag)

        total_count++;

    flag = true;

    index = 0;

    for (int j = 0; j < size; j++) {


        if (temp[i] == words[j][0]) {


            temp_index = i;



            while (words[j][index] && temp[temp_index]) {


                if (words[j][index] != temp[temp_index]) {


                    index = 0;

                    break;

                }

                index++;

                temp_index++;

            }

            if (words[j][index] == 0) {




                flag = false;

                i = temp_index - 1;

                total_count++;

                break;

            }

        }

    }



}

if (flag)

    total_count++;



return total_count;

}