[Pro] 리스트 복사

문제

파이썬 리스트의 기능들 중 일부를 구현하는 프로그램을 작성해야 한다.

구현해야 하는 API는 다음과 같다.

void init()
void copyList(char mDest[], char mSrc[], bool mCopy)
void updateElement(char mName[], int mIndex, int mValue)
int element(char mName[], int mIndex)

void init()

각 테스트 케이스의 시작 시 호출된다.

기존에 생성된 모든 리스트 정보를 초기화한다.

테스트 케이스 시작 시 생성되어 있는 리스트는 없다.

void makeList(char mName[], int mLength, int mListValue[])

새로운 리스트 mName을 생성한다.

mName은 아직 생성되지 않은 리스트 이름임이 보장된다.

생성된 리스트의 길이는 mLength이며, 각 원소는 다음과 같이 설정된다.

mName = [mListValue[0], mListValue[1], ..., mListValue[mLength - 1]]

조건은 다음과 같다.

• 리스트 이름의 길이: 1 이상 20 이하
• 리스트 길이: 1 이상 200,000 이하
• 각 원소의 값: 0 이상 32,767 이하

void copyList(char mDest[], char mSrc[], bool mCopy)

기존 리스트 mSrc를 복사하여 새로운 리스트 mDest를 생성한다.

mDest는 아직 생성되지 않았고, mSrc는 이미 생성되어 있음이 보장된다.

• mCopy == true

리스트의 모든 값을 복사한다.

mDest = mSrc.copy()

복사 이후 두 리스트는 서로 독립적이다.

• mCopy == false

리스트의 주소만 복사한다.

mDest = mSrc

두 리스트는 같은 리스트를 가리키므로, 한쪽에서 원소를 수정하면 다른 쪽에서도 변경된 값이 보인다.

• 리스트 이름의 길이: 1 이상 20 이하
• mCopy: true 또는 false

void updateElement(char mName[], int mIndex, int mValue)

mName 리스트의 mIndex번째 원소를 mValue로 변경한다.

mName[mIndex] = mValue

mName은 이미 생성된 리스트임이 보장된다.

• 리스트 이름의 길이: 1 이상 20 이하
• mIndex: 0 이상 mName 리스트의 길이 - 1 이하
• mValue: 0 이상 32,767 이하

int element(char mName[], int mIndex)

mName 리스트의 mIndex번째 원소 값을 반환한다.

mName은 이미 생성된 리스트임이 보장된다.

• 리스트 이름의 길이: 1 이상 20 이하
• mIndex: 0 이상 mName 리스트의 길이 - 1 이하

문제 제약 사항은 다음과 같다.

• 각 테스트 케이스 시작 시 init() 함수가 호출된다.
• 각 테스트 케이스에서 makeList() 함수의 호출 횟수는 10 이하이다.
• 각 테스트 케이스에서 copyList() 함수의 호출 횟수는 5,000 이하이다.
• 각 테스트 케이스에서 updateElement() 함수의 호출 횟수는 100,000 이하이다.
• 각 테스트 케이스에서 element() 함수의 호출 횟수는 400 이하이다.
• 리스트의 이름은 길이 1 이상, 20 이하의 알파벳 소문자로 이루어진 문자열이며, 문자열의 끝에는 ‘\0’이 추가되어 있다.
• 메모리 제한은 256MB이다.

설명

makeList(), copyList()로 인해 생성될 수 있는 리스트는 최대 5010개이다. 리스트의 길이는 최대 200,000이므로, 5,000 * 200,000 = 10억 개의 원소들이 존재하게 된다. int형 원소이면 4바이트이므로 각 리스트마다 길이 200,000인 배열을 독립적으로 가지게 되면 메모리 제한인 256MB를 넘게 된다.

또한 복사 및 수정 메서드는 비교적 자주 호출되고, 조회는 드물게 호출된다. 즉, 복사 및 수정 메서드는 빠르게 처리해야 하며, 조회 메서드는 상대적으로 느려도 괜찮다.

가장 간단하게, 각 리스트를 실제 배열로 가지는 방식을 생각해보자.

makeList(), copyList()에서 값 복사 방식은 $O(L)$, 나머지 메서드는 $O(1)$의 복잡도를 가진다.

단, 이 방식은 위에서 살펴본 바와 같이 메모리 제한을 넘게 된다.

복사 직후에는 두 배열의 값이 모두 같아야 하고, 깊은 복사인 경우 이후 서로 영향을 주면 안 된다. 처음 복사가 발생하면 같은 배열 상태를 바라보도록 하고, 깊은 복사인 경우 현재 상태를 복사 시점의 상태에 현재 배열에 발생한 변경 사항들을 적용하는 방식을 생각할 수 있다. updateElement()가 하나의 인덱스 값만 바꾸기 때문에, 어느 리스트에서 몇 번 인덱스를 어떤 값을 바꿨는지만 관리하면 된다.

수정 발생 시 변경된 배열 전체를 관리하는 경우 깊은 복사 및 수정이 반복되는 경우 메모리 초과가 발생할 수 있다.

이 방식으로 배열 복사 및 수정 메서드는 빠르게, 원소 수정 메서드는 상대적으로 느리게 동작하도록 할 수 있다.

단, 깊은 복사에서 변경 이력까지 함께 복사하면 변경 사항이 많은 경우 병목이 발생할 수 있다. 따라서 각 리스트가 전체 변경 내역을 가지는 것이 아니라 현재 상태의 마지막 변경이 무엇인지를 알도록 한다.

추가로 얕은 복사인 경우, 리스트 이름이 리스트 객체를 분리하도록 구현해야 다른 이름을 가진 리스트 이름이 같은 리스트 객체를 가리키도록 할 수 있다.

위와 같이 구현하면, 원소 수정 메서드는 현재 리스트의 가장 최근 변경부터 마지막 변경 방향으로 이동하며, 원하는 인덱스를 변경한 기록을 처음 발견하면 그 값을, 끝까지 찾지 못했다면 초기 배열의 값을 리턴하도록 하면 된다.

먼저 리스트 이름과 실제 리스트 객체를 분리해야 하고, 리스트 이름으로 실제 리스트를 빠르게 찾을 수 있어야 하므로, 해시맵인 unordered_map이 적절하다.

최초 배열은 실제로 수정 및 삽입, 삭제가 발생하지 않으므로 vector를 사용해도 무방하다.

변경 이력을 저장할 때, 저장해야 하는 정보는 인덱스와 값이다. 또한 어떤 변경 사항이 있었는지 순차적으로 알아야 하므로 연속적으로 이력들을 볼 수 있어야 한다. 논리적으로 본다면 연결 리스트 형태이나, 변경 횟수의 최대 횟수가 정해져 있으므로 단순 배열로 관리해도 된다.

또한 실제 리스트 간 어느 변경 이력부터 진행되었는지 알아야 하므로 이를 저장하는 배열이 추가로 필요하다.

코드

#include <cstring>
#include <string>
#include <unordered_map>

using namespace std;

#define MAX_BASE_LIST 10
#define MAX_LENGTH 200000
#define MAX_LIST 6000
#define MAX_EVENT 110000

// makeList로 생성된 원본 배열
int baseList[MAX_BASE_LIST][MAX_LENGTH];
int baseCount;

// 하나의 변경 이력
struct Event {
    int index;
    int value;
    int prev;
};

Event eventList[MAX_EVENT];
int eventCount;

// 각 실제 리스트가 가리키는 마지막 변경 이력
int lastEvent[MAX_LIST];
int listCount;

// 리스트 이름 -> 실제 리스트 번호
unordered_map<string, int> listId;

void init()
{
    baseCount = 0;
    eventCount = 0;
    listCount = 0;
    listId.clear();
}

void makeList(char mName[], int mLength, int mListValue[])
{
    // 원본 배열 저장
    for (int i = 0; i < mLength; i++)
        baseList[baseCount][i] = mListValue[i];

    // index가 -1이면 원본 배열을 가리키는 시작 이벤트
    eventList[eventCount] = {-1, baseCount, -1};

    listId[string(mName)] = listCount;
    lastEvent[listCount] = eventCount;

    baseCount++;
    eventCount++;
    listCount++;
}

void copyList(char mDest[], char mSrc[], bool mCopy)
{
    int srcId = listId[string(mSrc)];

    if (mCopy) {
        // 깊은 복사: 새로운 실제 리스트를 만들고 현재 변경 이력을 공유
        listId[string(mDest)] = listCount;
        lastEvent[listCount] = lastEvent[srcId];
        listCount++;
    }
    else {
        // 얕은 복사: 같은 실제 리스트를 가리킴
        listId[string(mDest)] = srcId;
    }
}

void updateElement(char mName[], int mIndex, int mValue)
{
    int id = listId[string(mName)];

    // 새로운 변경 이력을 마지막에 연결
    eventList[eventCount] = {mIndex, mValue, lastEvent[id]};
    lastEvent[id] = eventCount;

    eventCount++;
}

int element(char mName[], int mIndex)
{
    int event = lastEvent[listId[string(mName)]];

    // 최근 변경부터 역순으로 탐색
    while (true) {
        if (eventList[event].index == mIndex)
            return eventList[event].value;

        // 해당 인덱스가 변경된 적이 없다면 원본 값 반환
        if (eventList[event].index == -1)
            return baseList[eventList[event].value][mIndex];

        event = eventList[event].prev;
    }
}

시간복잡도

init()은 unordered_map의 원소들을 삭제하는데 $O(C)$의 시간복잡도를 가진다. C는 원소의 수이다. makeList()는 초기 배열을 복사하는데 $O(L)$의 시간복잡도를 가진다. copyList()는 리스트 번호와 마지막 변경 위치만 복사하고, updateElement()는 변경 이벤트를 하나 추가하므로 평균 $O(1)$이다. element()는 최근 변경부터 원하는 인덱스를 찾을 때까지 탐색하므로 $O(K)$이다. K는 특정 리스트의 변경 이력의 길이이다.

공간복잡도

원본 리스트 전체 크기, 전체 변경 횟수, 실제 리스트의 수, 리스트 이름의 수만큼의 복잡도를 갖는다.