상세 컨텐츠

본문 제목

프로그래머스쿨 C언어 레벨1 : 달리기 경주

개발이야기/C or C++ 언어 관련

by mycatdid0 2023. 8. 22. 16:00

본문

반응형

(작성일 2023.08.21.)

 


문제

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/178871

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제 설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.
선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

정답예제

프로그래스쿨 level1 문제 답안
프로그래스쿨 level1 문제 답안

 


풀이

 

본 문제에서 필요한 지식은 다음과 같이 나누어 볼 수 있습니다.

  1. 문자열 2차원 배열
  2. 문자열 검색
  3. 문자열 간에 Swap
  4. 검색 속도를 높이기 위한 최적화

1. 문자열 2차원 배열

코드에서 주어지는 값은 아래와 같습니다.

// players_len은 배열 players의 길이입니다.
// callings_len은 배열 callings의 길이입니다.
// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
char** solution(const char* players[], size_t players_len, const char* callings[], size_t callings_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    char** answer = (char**)malloc(1);

 

아래의 인자를 이해하는 것이 중요합니다.

const char* players[]

 

players는 이중 포인터입니다. player[0] player[1] player[2]...  의 각 배열값은 문자열 포인터를 저장하고 있습니다.

player변수의 자료 구조
player변수의 자료 구조

 

문제의 내용을 보면 각 문자열의 내용은 변하지 않으므로, 답안을 만들때 문자열(char)을 모두 복사하지 않고 문자열포인터(char*)만 복사하여 사용할 수 있습니다. 따라서 answer는 players에서 문자열포인터만 복사해오면 됩니다. answer에 메모리를 확보하고 players의 문자열포인터들을 복사하는 코드는 다음과 같습니다.

char** solution(const char* players[], size_t players_len, const char* callings[], size_t callings_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    char** answer = (char**)malloc(players_len *sizeof(char*));
    size_t i;
    
    for( i = 0; i < players_len; i++ ) {
        answer[i] = players[i];
    }

2. 문자열 검색

C언어에서 문자열 검색에 주로 사용되는 함수는 strcmp() 입니다.

함수원형 : int strcmp( const char *string1, const char *string2);
헤더파일 : string.h

ㅇ 설명 : string1과 string2를 문자열을 비교합니다.
 const char* 형을 받도록 되어 있으나, char* 형을 받아도 컴파일경고만 발생하고 빌드 및 실행 가능합니다.

ㅇ 리턴값
 0 : 두 문자열이 일치합니다.
 -1 : 두 문자열을 비교하였을때, 첫번째 다른 문자값이 string1 쪽값이 더 작을 때 -1을 리턴합니다.
  예) string1 = "aa1"아고 string2 = "aa3"일때, 각 문자열을 비교하여 세번째 값이 '1'와 '3'이므로
    string1인 '1'의 코드값이 string2의 '3'코드값보다 작음. 따라서 -1이 리턴됨
 1 : 두 문자열을 비교하였을때, 첫번째 다른 문자값이 string1 쪽값이 더 클때 1을 리턴합니다.
  예) string1 = "aa4"아고 string2 = "aa2"일때, 각 문자열의 세번째 값이 '4'와 '2'이므로
    string1인 '4'의 코드값이 string2의 '2'코드값보다 큼. 따라서 1이 리턴됨

 

callings의 각 문자열을 players의 각 문자열에서 찾으려면 아래와 같이 작성합니다. 각 callings의 문자열과 일치하는 answers문자열을 찾습니다.

int cnt, j;
for (cnt = 0; cnt < callings_len; cnt++)
{
    for (j = 0; j < players_len; j++)
    {
        if (strcmp(answers[j], callings[cnt]) == 0)
        {
            // answers에서 callings[cnt]문자열을 찾았다.
            // answers[j] 문자열과 answer[j-1] 문자열을 swap한다.
            break;
        }
    }
}

 

3. 문자열 간 swap

1번에서 2차원 포인터에 대해 이해하셨다면, 어렵지 않습니다. 문자(char)값들은 그대로 두고 문자열포인터끼리만 swap하면 됩니다.

// answers[j] 문자열과 answer[j-1] 문자열을 swap한다.
char *back;
back = answer[j];
answer[j] = answer[j - 1];
answer[j - 1] = back;

 


알고리즘은 맞지만 속도 초과로 실패

 

1번~3번의 내용을 정리하여 아래의 코드를 작성합니다.

더보기
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// #define DBG

// players_len은 배열 players의 길이입니다.
// callings_len은 배열 callings의 길이입니다.
// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
char **solution(const char *players[], size_t players_len, const char *callings[], size_t callings_len)
{
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    char **answer = (char **)malloc(players_len * sizeof(char *));
    char *back;
    size_t i;
    size_t cnt;

    for (i = 0; i < players_len; i++)
    {
        answer[i] = players[i];
    }

#ifdef DBG
    for (i = 0; i < players_len; i++)
    {
        printf("%s %s %u %s %u\n", players[i], p0[i].name, p0[i].index, p1[i].name, p1[i].index);
    }
#endif

    for (cnt = 0; cnt < callings_len; cnt++)
    {
        for (i = 0; i < players_len; i++)
        {
            if (strcmp(answer[i], callings[cnt]) == 0)
            {
                back = answer[i - 1];
                answer[i - 1] = answer[i];
                answer[i] = back;
                break;
            }
        }
    }

#ifdef DBG
    for (i = 0; i < players_len; i++)
    {
        printf("%s %s\n", players[i], answer[i]);
    }
#endif

    return answer;
}

 

코드를 제출하면 아래와 같이 시간초과로 실패합니다. 

테스트 1 〉	통과 (0.01ms, 4.14MB)
테스트 2 〉	통과 (0.02ms, 4.2MB)
테스트 3 〉	통과 (0.04ms, 4.19MB)
테스트 4 〉	통과 (0.25ms, 4.46MB)
테스트 5 〉	통과 (5.77ms, 4.17MB)
테스트 6 〉	통과 (23.79ms, 4.67MB)
테스트 7 〉	통과 (560.94ms, 8.84MB)
테스트 8 〉	통과 (2192.80ms, 13.9MB)
테스트 9 〉	통과 (8189.84ms, 24.2MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	통과 (0.01ms, 4.21MB)
테스트 15 〉	통과 (0.01ms, 4.21MB)
테스트 16 〉	통과 (0.01ms, 4.21MB)

 

시간초과가 발생한 이유는, answer에서 callings 문자열을 찾는 2중루프에서 최악의 경우 callings_len * players_len 만큼의 문자열 비교를 하기 때문입니다.

시간 초과 문제를 해결하기 위한 작업이 필요합니다.

 

 


검색속도를 줄이기 위한 알고리즘

 

 

지금까지, 문제에서 요구하는 문자열 검색코드를 작성하여 문제를 해결하였습니다. 그러나 '시간 초과'라는 예상치 못한 문제를 해결하여야 합니다.

 

검색의 속도를 높이는 방법은 다양합니다.

  1. 이진검색
  2. 해시테이블
  3. 인덱싱
  4. 알고리즘최적화

이 포스팅에서는 아래의 같이 알고리즘을 작성하였습니다.

  1. 검색을 최대속도로 하기 위하여 미리 정렬한다.
  2. 미리 정렬한 데이터 p1와 answer를 연결하는 인덱스를 사용한다.

 

1. 미리 정렬한다.

C언어에서는 sort 함수가 기본 라이브러리에 포함되어 있지 않습니다. 문제를 푸는 중에 sort알고리즘의 오류검증까지 할 수는 없으므로, 간단한 sort 코드를 외워두는 것이 좋습니다. 간단하고 성능이 적당한 insert sort 코드를 사용하였습니다.
정정 : c언어 라이브러리에 qsort() 함수가 이미 있었습니다.

void insert_sort(int *p1, int p1_cnt)
{
    int i, j;
    int key;

    for (i = 0; i < p1_cnt; i++)
    {
        key = p1[i];

        for (j = i - 1; j >= 0 && key > p1[j]; j--)
        {
            p1[j + 1] = p1[j];
        }
        p1[j + 1] = key;
    }
}

 

배열을 한번 정렬해 놓으면, 2진 검색을 사용하여 빠르게 검색합니다.

int bin_search(int* p1, int p1_cnt, int search)
{
    int left = 0;
    int right = p1_cnt;
    int pos;
    int cmp;

    pos = (left + right) / 2;
    while ((cmp = search -p1[pos]) != 0)
    {
        if (cmp < 0)
            left = pos;
        else
            right = pos;

        pos = (left + right) / 2;
    }

    return pos;
}

 

2. 인덱스를 사용한다.

1번에서 미리 정렬된 배열을 통해 빠르게 문자열을 검색한 다음엔, 검색결과가 answer에서 어느 위치에 해당하는지를 파악해야 합니다. 인덱스 적용을 위하여 {문자열, 인덱스}의 구조체를 만들었습니다.

 

struct t_players
{
    char *name;
    size_t index;
};
struct t_players p1[50001]; // 이름순 정렬

 

player를 answer에 복사할 때, 인덱스용 구조체 배열인 p1에 똑같이 복사하고 index를 업데이트합니다.

    for (i = 0; i < players_len; i++)
    {
        answer[i] = players[i];

        p1[i].name = players[i];
        p1[i].index = i;
    }

 

다음과 같이 알고리즘을 구성합니다.

  • 미리 정렬된 p1에서 문자열을 검색
  • 찾아낸 p1값의 인덱스를 통해 answer위치를 찾음
  • 문제의 요구대로 answer[]와 바로앞 answer[]를 서로 swap 함
  • swap된 answer의 인덱스를 p1에 업데이트
    for (cnt = 0; cnt < callings_len; cnt++)
    {
        int where = where_name(callings[cnt]);
#ifdef DBG
        printf("%s %s %u\n", callings[cnt], p1[where].name, p1[where].index);
#endif

        int ans_pos = p1[where].index; // 실제 배열 위치를 찾아서,
        // 배열와 앞의 값과 뒤의 값을 교체
        back = answer[ans_pos - 1];
        answer[ans_pos - 1] = answer[ans_pos];
        answer[ans_pos] = back;
        // p1의 필요한 값에 업데이트
        p1[where].index--;
        where = where_name(answer[ans_pos]);
        p1[where].index++;
    }

 


완성된 코드

더보기
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// #define DBG

struct t_players
{
    char *name;
    size_t index;
};
struct t_players p1[50001]; // 이름순 정렬
struct t_players pt;        // temp

size_t g_players_len;

void insert_sort_p1()
{
    int i, j;

    for (i = 0; i < g_players_len; i++)
    {
        pt.name = p1[i].name;
        pt.index = p1[i].index;

        for (j = i - 1; j >= 0 && strcmp(p1[j].name, pt.name) > 0; j--)
        {
            p1[j + 1].name = p1[j].name;
            p1[j + 1].index = p1[j].index;
        }
        p1[j + 1].name = pt.name;
        p1[j + 1].index = pt.index;
    }
}

int where_name(char *fname)
{
    int left = 0;
    int right = g_players_len;
    int pos;
    int cmp;

    pos = (left + right) / 2;
    while ((cmp = strcmp(p1[pos].name, fname)) != 0)
    {
        if (cmp < 0)
            left = pos;
        else
            right = pos;

        pos = (left + right) / 2;
    }

    return pos;
}

// players_len은 배열 players의 길이입니다.
// callings_len은 배열 callings의 길이입니다.
// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
char **solution(const char *players[], size_t players_len, const char *callings[], size_t callings_len)
{
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    char **answer = (char **)malloc(players_len * sizeof(char *));
    char *back;
    size_t i;
    size_t cnt;

    g_players_len = players_len;

    for (i = 0; i < players_len; i++)
    {
        answer[i] = players[i];

        p1[i].name = players[i];
        p1[i].index = i;
    }

    insert_sort_p1();

#ifdef DBG
    for (i = 0; i < players_len; i++)
    {
        printf("%s %s %u %s %u\n", players[i], p0[i].name, p0[i].index, p1[i].name, p1[i].index);
    }
#endif

    for (cnt = 0; cnt < callings_len; cnt++)
    {
        int where = where_name(callings[cnt]);
#ifdef DBG
        printf("%s %s %u\n", callings[cnt], p1[where].name, p1[where].index);
#endif

        int ans_pos = p1[where].index; // 실제 배열 위치를 찾아서,
        // 배열와 앞의 값과 뒤의 값을 교체
        back = answer[ans_pos - 1];
        answer[ans_pos - 1] = answer[ans_pos];
        answer[ans_pos] = back;
        // p1의 필요한 값에 업데이트
        p1[where].index--;
        where = where_name(answer[ans_pos]);
        p1[where].index++;
    }

#ifdef DBG
    for (i = 0; i < players_len; i++)
    {
        printf("%s %s\n", players[i], answer[i]);
    }
#endif

    return answer;
}

 

qsort() 적용 코드

더보기
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// #define DBG

struct t_players
{
    char *name;
    size_t index;
};
struct t_players p1[50001]; // 이름순 정렬
struct t_players pt;        // temp

size_t g_players_len;

int qsort_compare( const void* a, const void *b) {
    return strcmp( ((struct t_players*)a)->name, ((struct t_players*)b)->name );
}

int where_name(char *fname)
{
    int left = 0;
    int right = g_players_len;
    int pos;
    int cmp;

    pos = (left + right) / 2;
    while ((cmp = strcmp(p1[pos].name, fname)) != 0)
    {
        if (cmp < 0)
            left = pos;
        else
            right = pos;

        pos = (left + right) / 2;
    }

    return pos;
}

// players_len은 배열 players의 길이입니다.
// callings_len은 배열 callings의 길이입니다.
// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
char **solution(const char *players[], size_t players_len, const char *callings[], size_t callings_len)
{
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    char **answer = (char **)malloc(players_len * sizeof(char *));
    char *back;
    size_t i;
    size_t cnt;

    g_players_len = players_len;

    for (i = 0; i < players_len; i++)
    {
        answer[i] = players[i];

        p1[i].name = players[i];
        p1[i].index = i;
    }

    qsort( p1, players_len, sizeof(struct t_players), qsort_compare);

#ifdef DBG
    for (i = 0; i < players_len; i++)
    {
        printf("%s %s %u\n", players[i], p1[i].name, p1[i].index);
    }
#endif

    for (cnt = 0; cnt < callings_len; cnt++)
    {
        int where = where_name(callings[cnt]);
#ifdef DBG
        printf("%s %s %u\n", callings[cnt], p1[where].name, p1[where].index);
#endif

        int ans_pos = p1[where].index; // 실제 배열 위치를 찾아서,
        // 배열와 앞의 값과 뒤의 값을 교체
        back = answer[ans_pos - 1];
        answer[ans_pos - 1] = answer[ans_pos];
        answer[ans_pos] = back;
        // p1의 필요한 값에 업데이트
        p1[where].index--;
        where = where_name(answer[ans_pos]);
        p1[where].index++;
    }

#ifdef DBG
    for (i = 0; i < players_len; i++)
    {
        printf("%s %s\n", players[i], answer[i]);
    }
#endif

    return answer;
}

마치며

 

여기까지, C언어에서 문자열검색과 인덱싱 알고리즘을 연습할 수 있는 '프로그래머스쿨 레벨1문제 달리기 경주 C언어 풀이'를 포스팅하였습니다.

문제를 푼 후에는, 문제화면 아레의 '다른사람의 풀이'를 꼭 확인하시기 바랍니다. 훌륭한 분들의 코드가 많습니다.

 

언제나 감사드립니다.

 

 

반응형

관련글 더보기

댓글 영역