[C언어 연습문제]강좌 14. Dynamic Array in C(도서관 책장, 책 페이지 수 쿼리, 조회 프로그램)

동적 배열의 활용 - 도서관 선반과 책 페이지 수 조회 프로그램 작성

학습(Study) & 목표(Objective) & 과제(Task)

Snow Howler는 HuskyLand시 중앙 도서관 사서입니다. 그는 다음 형식의 요청을 처리해야 합니다.

- 1 x y : x 번째 책장의 끝에 y page의 책을 추가해야 합니다.(유형 1)

- 2 x y : x 번째 책장에 y번째 책의 page의 수를 출력해야 합니다. (유형 2)

- 3 x : x 번째 책장에 있는 책이 몇 권인지 출력해야 합니다.(유형 3)

Snow Howler에게는 교육부에서 투입한 조교 Oshie가 있습니다. Oshie는 경험이 없지만, 유형2와 유형3의 모든 쿼리를 처리할 수 있습니다.

Snow Howler는 유형 1의 모든 쿼리를 처리할 수 있도록 도와줘야 합니다.

Oshie는 2개의 동적 배열을 사용하였습니다.

int * total_number_of_books;

/*

 * 각 책장의 총 책의 권수를 저장하는 배열

 */

int** total_number_of_pages;

/*

 * 책장의 각 책의 페이지 수를 저장하는 배열

 * 행은 책장을 나타내고, 열은 책을 나타낸다.

 */

입력 형식(Input Format)

첫 번째 줄에는 도서관 책장 수인 total_number_of_shelves가 입력됩니다.

두 번째 줄에는 정수 total_number_of_queries에 요청 수가 입력됩니다.

다음 줄 부터 total_number_of_queries의 요청만큼 각각 세가지 형식 중 하나의 형식으로 요청을 포함합니다.

제약 조건(Constraints)

-  (책장 수)

-  (요청 수)

- 유형2의 각 쿼리에 대해서는 x책장의 y 검색어에 대해 책이 색인된 책장에 있음을 보장합니다.

- 

- (x책장의 범위)

- 책과 책장은 모두 0부터 번호를 부여받습니다.

- (책장 당 최대 도서의 수) <= 1100

출력 형식(Output Format)

유형1 요청에 대한 로직을 처리해야 합니다. 이 로직은 유형2와 유형3에 대한 요청을 제공합니다.

입력 예제(Sample Input)

5

5

1 0 15

1 0 20

1 2 78

2 2 0

3 0

출력 예제(Sample Output)

78

2

설명(Explanation)

5개의 책장과 5개의 요청 쿼리가 있습니다.

입력 요청은 다음과 같습니다.

1. 0번째 책장의 끝에 15 page 분량의 책을 놓습니다.(유형 1)

2. 0번째 책장의 끝에 20 page 분량의 책을 놓습니다.(유형 1)

3. 2번째 책장의 끝에 78 page 분량의 책을 놓습니다.(유형 1)

4. 2번째 책장에 놓여 있는 0번째 책의 페이지 수는 78입니다.(유형 2)

5. 0번째 책장에 있는 책의 수는 2개 입니다.(유형 3)

주어진 코드

#include <stdio.h>
#include <stdlib.h>
 
/*
 * This stores the total number of books in each shelf.
 */
int* total_number_of_books;
 
/*
 * This stores the total number of pages in each book of each shelf.
 * The rows represent the shelves and the columns represent the books.
 */
int** total_number_of_pages;
 
int main()
{
    int total_number_of_shelves;
    scanf("%d", &total_number_of_shelves);
    
    int total_number_of_queries;
    scanf("%d", &total_number_of_queries);
    
    while (total_number_of_queries--) {
        int type_of_query;
        scanf("%d", &type_of_query);
        
        if (type_of_query == 1) {
            /*
             * Process the query of first type here.
             */
            int x, y;
            scanf("%d %d", &x, &y);
 
        } else if (type_of_query == 2) {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%d\n", *(*(total_number_of_pages + x) + y));
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", *(total_number_of_books + x));
        }
    }
 
    if (total_number_of_books) {
        free(total_number_of_books);
    }
    
    for (int i = 0; i < total_number_of_shelves; i++) {
        if (*(total_number_of_pages + i)) {
            free(*(total_number_of_pages + i));
        }
    }
    
    if (total_number_of_pages) {
        free(total_number_of_pages);
    }
    
    return 0;
}

코드가 주어져 있습니다. 제시된 코드에는 2개의 전역 포인트 변수를 동적 배열로 만들 준비를 하고 있고, 선반의 수와 쿼리 수를 입력받아 유형 2와 유형 3을 처리하고 있는 코드입니다.

Process the query of first type here 주석 부분에 유형 1을 처리 해주면 될 것 같습니다.

답안 코드

C에서 동적 배열은 할당된 메모리를 가리키는 포인터로 표현됩니다. stdlib.h에 구현된 malloc 함수나 calloc 함수로 동적 배열을 구현할 수 있습니다.

책을 추가할 때, 동적 배열 total_number_of_books의 배열, 즉 책장에 대응되는 배열 값을 증가시켜야 합니다. total_number_of_books 배열에 대응하는 값을 증가시키기는 쉽지 않을 수 있는데, total_number_of_books[x] 크기의 새 배열을 만들고, 이전 값을 복사, 끝에 y를 추가합니다. 그리고 free() 함수를 호출해서, 이전에 할당된 메모리를 비운 다음 새 배열에 다시 할당하는 작업을 반복합니다.

여기서는 메모리를 다시 할당해주는 realloc() 함수를 사용해서 문제를 풀어보겠습니다.

int main()
{
    int total_number_of_shelves;
    scanf("%d", &total_number_of_shelves);
 
    int total_number_of_queries;
    scanf("%d", &total_number_of_queries);
 
    total_number_of_books =
                (int *)malloc(total_number_of_shelves * sizeof(int));
            total_number_of_pages =
                (int **)malloc(total_number_of_shelves * sizeof(int*));
    while (total_number_of_queries--) {
        int type_of_query;
        scanf("%d", &type_of_query);
        
 
        if (type_of_query == 1) {
            /*
             * Process the query of first type here.
             */
 
             int x, y;
            scanf("%d %d", &x, &y);
            total_number_of_books[x]++;
            total_number_of_pages[x] =
                (int *)realloc(total_number_of_pages[x],
                               total_number_of_books[x] * sizeof(int));
            total_number_of_pages[x][total_number_of_books[x]-1]=y;
 
        } else if (type_of_query == 2) { ... 
}

우선 동적 main 함수에 동적 배열을 만듭니다. total_number_of_books는 1차원 동적 배열을 만들기 위해 (int *) 형식의 메모리를 책장 수 만큼 할당하고, total_number_of_pages는 2차원 배열을 만들어야 하므로 먼저 1차원(책장) index의 메모리만큼을 할당합니다.

그리고 query가 돌면서 유형을 검사하면서 처리를 하게 되는데, type_of_query 2, 3은 구현이 되어있고, hacker rank에서는 수정할 수 없게 막혀있었습니다. 따라서 type_of_query == 1 조건만 처리하면 됩니다.

total_number_of_books[x]는 이미 메모리를 할당해서 책장 수 범위 안에만 들어가면 문제가 없습니다. 입력받은 x번째 책장에 책을 추가(total_number_of_books[x]++)하고, 페이지를 추가(total_number_of_pages[x][total_number_of_books[x]-1] =y)하면 됩니다.

page를 추가하기 전에, 페이지값을 저장하는 메모리를 할당해주어야 하는데, 매번 할당하고, 초기화하는 작업 대신 메모리를 다시 할당해주는 realloc() 함수를 이용해서 책의 수(total_number_of_books[x]) 만큼의 메모리를 할당해주면 될 것 같습니다.

여기서 중요한 점은 total_number_of_books와 total_number_of_pages는 별도로 운용되는 배열로, total_number_of_books[] 값이 변경된다고 해도, total_number_of_pages[] 값이 변하는 것이 아니므로 별도로 잘 처리해주어야 합니다.

total_number_of_books[x]-1 에서 -1을 해주는 이유는 total_number_of_books[x]++로 책장의 책 수를 위에서 증가시켜서 그런데, 확인은 안 해봤지만, 아래와 같이 스타일대로 처리를 해주시면 되겠습니다.

total_number_of_pages[x] = (int *)realloc(total_number_of_pages[x],
        (total_number_of_books[x]+1) * sizeof(int));
total_number_of_pages[x][total_number_of_books[x]]=y;
total_number_of_books[x]++;

+1과 -1이 발생하는 이유는 책장의 수를 셀 때는 1부터 시작하고, 배열 index는 0부터 시작하는 부분 때문입니다. 입력받은 후 책 수를 먼저 증가시키고 처리를 할지, 처리하고 증가시킬지의 차이라고 보시면 될 것 같습니다.

추가 답안 코드

#include <stdio.h>
#include <stdlib.h>
 
/*
 * This stores the total number of books in each shelf.
 */
int* total_number_of_books;
 
/*
 * This stores the total number of pages in each book of each shelf.
 * The rows represent the shelves and the columns represent the books.
 */
int** total_number_of_pages;
 
enum eExceptMode
{
    eModeNone = 0,
 
    eModeType1,
    eModeType2,
    eModeType3,
    eModeTotal,
 
    eModeMax
};
 
int ExceptionCatch(enum eExceptMode mode, int x, int y)
{
    int nExcept = 0;
    switch (mode)
    {
    case eModeType1:
        if(x < 0 || x >= y)
            nExcept = 1;
        break;
    case eModeType2:
        break;
    case eModeType3:
        break;
    case eModeTotal:
    default:
        if (x < 1 || x > 1000000)
            nExcept = 1;
        if (y < 1 || y > 1000000)
            nExcept = 1;
        break;
  } // end switch
 
  return nExcept;
}
              
int main()
{
    // 책장 수 입력
    int total_number_of_shelves = 0;
    scanf("%d", &total_number_of_shelves);
    
    // 쿼리 수 입력
    int total_number_of_queries = 0;
    scanf("%d", &total_number_of_queries);
    int nExcept = 0;
    nExcept = ExceptionCatch(eModeTotal, total_number_of_shelves,
                                            total_number_of_queries);
    if(nExcept)
    {
        printf("Error : Total Number");
        return -1;
    }
    
    // 책장 수 만큼 배열 할당
    total_number_of_books = (int *)malloc(total_number_of_shelves * sizeof(int));
    total_number_of_pages = (int **)malloc(total_number_of_shelves * sizeof(int*));
 
    for (int i = 0; i < total_number_of_shelves; i++)
    {
        //각 책장의 책 수를 초기화
        total_number_of_books[i] = 0;
    }
 
    while (total_number_of_queries--)
    {
        int type_of_query = 0;
        scanf("%d", &type_of_query);
        
        if (type_of_query == 1)
        {
            int x = 0, y = 0;
            scanf("%d %d", &x, &y);
            nExcept = ExceptionCatch(eModeType1, x, total_number_of_shelves);
            if (nExcept)
            {
              printf("Input condition error.");
              total_number_of_queries++;
              continue;
            }
 
            total_number_of_books[x]++; // 선반에 있는 책 수 증가
            //책수 만큼 배열 index 할당
            total_number_of_pages[x] = (int *)realloc(total_number_of_pages[x],
                               total_number_of_books[x] * sizeof(int));
 
            total_number_of_pages[x][total_number_of_books[x] - 1] = y;
 
        } else if (type_of_query == 2) {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%d\n", *(*(total_number_of_pages + x) + y));
        } else {
            int x;
            scanf("%d", &x);
            printf("%d\n", *(total_number_of_books + x));
        }
    }
 
    if (total_number_of_books) {
        free(total_number_of_books);
    }
    
    for (int i = 0; i < total_number_of_shelves; i++) {
        if (*(total_number_of_pages + i)) {
            free(*(total_number_of_pages + i));
        }
    }
    
    if (total_number_of_pages) {
        free(total_number_of_pages);
    }
    
    return 0;
}

C언어에 맞게 예외처리 함수를 넣어보았습니다. 유심히 살펴보지 않아 문제점이 있을 수도 있는데요, 입력 조건을 검사하는 목적으로 작성하였습니다. 일반적으로, 실무에서는 개발 시간보다 유지보수 시간에 투자를 더 많이 하기 되는 경우가 대부분이기 때문에, 이렇게 미리 예외처리를 하는 습관을 만들어두면, 업무 시간을 효율적으로 쓸 수 있을 것 같습니다.

물론 C++, C#, JAVA 등의 고급언어로 가면서 예외처리 문법(try, catch)을 숙지하셔서 사용하시는 것도 좋은 습관인 것 같습니다.