백준 23309번 철도 공사: C언어 풀이

백준 23309번 철도공사 문제의 C 언어 풀이 해설입니다.
연결 리스트를 배열로 대체하여 시간 초과를 해결하는 방법을 소개합니다.

전략

원형 연결 리스트 쓰지 않기

노드 만들고, 메모리 할당하고, 연결하고... 열심히 만들어봐도 계속 시간 초과가 났다.
역시 기본 개념만으로 골드 문제의 벽을 넘는 건 불가능한가? 라고 생각하던 와중에 하나의 아이디어가 떠올랐다.

고유번호 i를 찾는 작업은 일반적인 연결 리스트에서 O(n)이 걸린다.
이때 고유번호 i를 인덱스로 갖는 배열을 만들면 O(1)으로 찾을 수 있다.

보통 연결 리스트는 앞/뒤 노드를 가르키는 포인터를 갖는다.
배열도 마찬가지로 앞/뒤 노드의 인덱스를 같이 넣어주면 연결 리스트 처럼 사용할 수 있다.

정수형으로 다음 역 번호와 이전 역 변호를 갖는 구조체 struct station을 만들어 배열에 넣어준다.

탐색 시간이 줄면서 시간 초과를 해결할 수 있다.

구조가 같아서 연결 리스트로 짠 코드를 배열으로 바꾸는 과정은 그리 어렵지 않았다.
오히려 메모리 할당 및 해제를 신경쓰지 않아도 되어 편리하기도 하다.

코드

#include <stdio.h>

#define MAX_STATION_ID 1000000

struct station
{
    int prev_id;
    int next_id;
};

enum operation
{
    BUILD = 'B',
    CLOSE = 'C',
    NEXT = 'N',
    PREV = 'P'
};

int main(void)
{
    // Array based on station id
    struct station station_arr[MAX_STATION_ID] = {{0, 0},};

    int num_stations;
    int num_operations;
    scanf("%d %d", &num_stations, &num_operations);

    int head = 0;    
    int last = 0;

    // Build circular station line
    for (int i = 0; i < num_stations; i++)
    {
        int station_id;
        scanf("%d", &station_id);
        station_arr[station_id].prev_id = last;
        station_arr[station_id].next_id = 0;

        station_arr[last].next_id = station_id;        
        last = station_id;
    }

    // Link first arr[head].next and last
    int first = station_arr[head].next_id;

    station_arr[first].prev_id = last;
    station_arr[last].next_id = first;

    for (int i = 0; i < num_operations; i++)
    {
        char operation[3];    // Holds BN, CN, etc.
        scanf("%s", operation);
        int id_i;
        int id_j = -1;
        scanf("%d", &id_i);

        struct station station_i = station_arr[id_i];
        // Print id based on option2
        printf("%d\n", (operation[1] == NEXT) ? station_i.next_id : station_i.prev_id);

        switch (operation[0])
        {
            case BUILD:
            {
                // Building station requires another id
                scanf("%d", &id_j);

                // Build between prev and next
                int prev = (operation[1] == NEXT) ? id_i : station_i.prev_id;
                int next = (operation[1] == NEXT) ? station_i.next_id : id_i;

                station_arr[id_j].next_id = next;
                station_arr[id_j].prev_id = prev;

                station_arr[prev].next_id = id_j;
                station_arr[next].prev_id = id_j;
                break;
            }
            case CLOSE:
            {   
                // Close station between prev and next
                int prev = (operation[1] == NEXT) ? id_i : station_arr[station_i.prev_id].prev_id;
                int next = (operation[1] == NEXT) ? station_arr[station_i.next_id].next_id : id_i;
                int close = (operation[1] == NEXT) ? station_i.next_id :  station_i.prev_id; 

                // Link prev and next, delete station
                station_arr[prev].next_id = next;
                station_arr[next].prev_id = prev;
                station_arr[close].next_id = 0;
                station_arr[close].prev_id = 0;
                break;
            }
        }
    }
}

후기

C로 푼 사람이 애초에 얼마 없기도 하지만, 언어 별 맞힌 사람 첫 페이지에 올라가니 감회가 새롭다.
도파민이 막 나온달까?