[ 백준 / C ] 25757번 : 임스와 함께하는 미니게임

25757

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

// 게임을 플레이한 횟수 구하기
int game_play_num(char game, int index){
    switch (game)
    {
    case 'Y':
        return index;
        break;
    case 'F':
        return index/2;
        break;
    case 'O':
        return index/3;
        break;
    }
}

// 비교 연산 
int cmp(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

int main(void){
    // 플레이 신청한 사람들 수, 게임 종류 입력
    int appli_num = 0;
    char games = 0; 
    scanf("%d %c", &appli_num, &games);
    
    char (*players)[21] = (char(*)[21]) malloc(sizeof(char)*appli_num*21);
    int index = 0;

    // 플레이어 입력 받기
    for(int i = 0; i < appli_num; i++){
        getchar();
        scanf("%s", players[i]);
    }

    // 정렬 qsort
    qsort(players, appli_num, sizeof(players[0]), cmp);

    // 중복 검사 후 중복이 아니면 count;
    int count = 1;
    for(int i = 1; i < appli_num; i++){
        if(strcmp(players[i], players[i-1]) != 0){
            count++;
        }
    }

    // 플레이 한 횟수 출력
    printf("%d", game_play_num(games ,count));
    free(players);
    return 0;
}

---

음..... 이 번 거는 인터넷도 찾아보고 gpt에게도 도움을 받았다.

 

처음 내 코드는 코드도 길고 O(n^2) 여서 자꾸 시간 초과가 났다.

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

int game_player_num(char game){
    switch (game)
    {
    case 'Y':
        return 1;
        break;
    case 'F':
        return 2;
        break;
    case 'O':
        return 3;
        break;
    }
}

int is_play_f(int index, char *name, char (*players)[21]){
    for(int i = 0; i < index; i++){
        if(strcmp(name, players[i])==0){
            return 1;
        }
    }
    return 0;
}

int main(void){
    int appli_num = 0;
    char games = 0; 
    scanf("%d %c", &appli_num, &games);
    
    int num = game_player_num(games);    
    char (*players)[21] = (char(*)[21]) malloc(sizeof(char)*appli_num*21);
    int index = 0, count = 0, cur_player = 0;

    for(int i = 0; i < appli_num; i++){
        getchar();
        char name[21] = {0};
        scanf("%s", name);

        int is_play = is_play_f(index, name, players);

        if(!is_play){
            cur_player ++;

            strcpy(players[index++], name);
            if(num == cur_player){
                count ++;
                cur_player = 0;
            }
        }
    }

    printf("%d", count);
    free(players)
    return 0;
}

근데 인터넷을 찾아보니 

if(!is_play){
            cur_player ++;

            strcpy(players[index++], name);
            if(num == cur_player){
                count ++;
                cur_player = 0;
            }
        }

 이부분을 이렇게 하지 않고 그냥 

int game_play_num(char game, int index){
    switch (game)
    {
    case 'Y':
        return index;
        break;
    case 'F':
        return index/2;
        break;
    case 'O':
        return index/3;
        break;
    }
}

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

int game_play_num(char game, int index){
    switch (game)
    {
    case 'Y':
        return index;
        break;
    case 'F':
        return index/2;
        break;
    case 'O':
        return index/3;
        break;
    }
}

int is_play_f(int index, char (*players)[21]){
    for(int i = 0; i < index; i++){
        if(strcmp(players[i], players[index])==0){
            return 1;
        }
    }
    return 0;
}

int main(void){
    int appli_num = 0;
    char games = 0; 
    scanf("%d %c", &appli_num, &games);
    
    char (*players)[21] = (char(*)[21]) malloc(sizeof(char)*appli_num*21);
    int index = 0;

    for(int i = 0; i < appli_num; i++){
        getchar();
        scanf("%s", players[index]);

        if(!is_play_f(index, players)){
            index++;
        }
    }



    printf("%d", game_play_num(games ,index));
    free(players);
    return 0;
}

이렇게도 적용할 수 있어서 이렇게 적용했지만, 당연하게도 이 부분에서 시간초과가 나는 것은 아니었다.

 

내 문제는 

플레이어 닉네임을 입력받으면서 O(n)
입력받을 때마다 중복 닉네임을 찾고, index는 최대로 appli_num까지 증가해 O(n^2)이 된 것..

 

 

 

계속 찾아보니 C++ 언어에서는 set 라이브러리가 있어서 set에 넣으면 중복은 없는 자료구조니까 빠르게 해결이 되었다.

근데, C는 set 라이브러리가 존재하지 않았다. 그래서 set을 직접 구현하거나, 다른 방법으로 풀 수밖에 없었다...

 

근데 도저히 어떻게 코드를 짜야하는지 모르겠어서...

채점 현황에서 C언어로 푸신 다른 분들이 있는지 확인해봤는데, 많은 분들이 시간 초과가 나셨지만 그래도 해결하신 분이 계셨다...

그래서 한 참 이 문제를 잡고 있다가 gpt에게 도움을 요청했다.

 

오... 똑똑한 gpt,,,

입력을 다 받고, O(n)

퀵정렬로 정렬한 뒤 O(nlogn)

앞에 인덱스와 비교해서 중복이 아닐 때 count를 하는 방법 O(n)

으로 풀 수 있다는 것을 알게 되었다. 
총 O(3 nlogn)

그래서 그렇게 풀었더니 맞았다...

---

사실 백준 문제를 풀 때 되도록이면 gpt를 사용하지 않고 있다.

내 실력을 키우기 위해서도 있고, 내가 더 생각했으면 좋겠어서 되도록이면 gpt를 사용하지 않고 있다.

 

근데 오늘 gpt를 사용해서 문제를 해결하니까... 뭔가 허탈함도 조금 있고, 이렇게 알아가면서 배우는 걸까?라는 생각도 든다...

 

위에 다른 분들의 코드 참고하는 부분도 그렇고 gpt가 만들어준 코드를 참고하는 것도 보면서 느낀 건데,

정말 항상 나보다 좋은 코드가 있구나 내가 부족하구나를 느끼게 된다. 

 

좀 더 나은 코드를 만들 수 있는 내가 되도록 노력해야지...