13072번: [Pro] 병사관리

문제

병사들을 관리하는 프로그램을 작성하려고 한다.

각 병사는 고유번호, 소속 팀, 평판 점수를 가지고 있다.

병사의 고유번호는 1 이상 100,000 이하이다. 팀 번호는 1 이상 5 이하이다. 평판 점수는 1 이상 5 이하이다. 병사를 고용하거나 해고할 수 있으며, 병사 한 명의 평판 점수를 변경하거나 특정 팀에 속한 모든 병사의 평판 점수를 변경할 수 있다.

또한 특정 팀에서 평판 점수가 가장 높은 병사를 검색할 수 있어야 한다. 평판 점수가 가장 높은 병사가 여러 명이라면 고유번호가 가장 큰 병사를 선택한다.

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

void init();
void hire(int mID, int mTeam, int mScore);
void fire(int mID);
void updateSoldier(int mID, int mScore);
void updateTeam(int mTeam, int mChangeScore);
int bestSoldier(int mTeam);

`void init()`

모든 병사 정보를 초기화한다.

테스트 케이스마다 처음 한 번 호출된다.
이전에 등록된 모든 병사 정보는 삭제된다.

`void hire(int mID, int mTeam, int mScore)`

병사를 고용한다.

매개변수	설명
`mID`	병사의 고유 ID
`mTeam`	소속 팀 (`1 ~ 5`)
`mScore`	평점 (`1 ~ 5`)

mID는 현재 고용되어 있는 다른 병사의 ID와 중복되지 않는다.

`void fire(int mID)`

병사를 해고한다.

매개변수	설명
`mID`	해고할 병사의 ID

mID에 해당하는 병사는 현재 고용되어 있음이 보장된다.
해고된 병사는 이후 다시 고용될 수 있다.

`void updateSoldier(int mID, int mScore)`

특정 병사의 평점을 변경한다.

매개변수	설명
`mID`	평점을 변경할 병사의 ID
`mScore`	변경할 평점 (`1 ~ 5`)

mID에 해당하는 병사는 현재 고용되어 있음이 보장된다.
병사의 소속 팀은 변경되지 않는다.

`void updateTeam(int mTeam, int mChangeScore)`

특정 팀에 속한 모든 병사의 평점을 한꺼번에 변경한다.

매개변수	설명
`mTeam`	평점을 변경할 팀 (`1 ~ 5`)
`mChangeScore`	평점 변화량 (`-4 ~ 4`)

각 병사의 새로운 평점은 다음과 같이 결정된다.

newScore = oldScore + mChangeScore

단, 계산 결과가 1 ~ 5 범위를 벗어나면 다음과 같이 보정한다.

newScore < 1  →  1
newScore > 5  →  5

`int bestSoldier(int mTeam)`

특정 팀에서 가장 우수한 병사의 ID를 반환한다.

매개변수	설명
`mTeam`	조회할 팀 (`1 ~ 5`)

선택 기준은 다음과 같다.

평점이 가장 높은 병사를 선택한다.
최고 평점의 병사가 여러 명이라면 ID가 가장 큰 병사를 선택한다.

반환값

조건을 만족하는 병사의 mID를 반환한다.

mTeam에는 최소 한 명 이상의 병사가 존재함이 보장된다.

제약사항은 다음과 같다.

병사의 고유번호는 1 이상 100,000 이하이다.
팀 번호는 1 이상 5 이하이다.
평판 점수는 1 이상 5 이하이다.
한 테스트 케이스에서 hire()는 최대 100,000번 호출된다.
한 테스트 케이스에서 fire()는 최대 100,000번 호출된다.
한 테스트 케이스에서 updateSoldier()는 최대 100,000번 호출된다.
한 테스트 케이스에서 updateTeam()은 최대 100,000번 호출된다.
한 테스트 케이스에서 bestSoldier()는 최대 100번 호출된다.

설명

특이한 제약사항을 먼저 찾아본다.

먼저 팀 번호와 평판 점수는 1 ~ 5 사이 값만 가능하다. 또한 bestSoldier()은 최대 100번만 호출된다.

가장 처음 할 수 있는 접근 방식은 병사 ID를 인덱스로 하는 배열에 병사 정보를 저장하는 것이다.

struct Soldier {
    int team;
    int score;
    bool hired;
};

Soldier soldiers[100001];

Soldier 구조체에 고용 여부 필드까지 관리한다면 hire(), fire(), updateSoldier() 는 $O(1)$ 에 처리 가능하다.

단, updateTeam() 과 bestSoldier()는 전체 병사를 순회해야 하므로 $O(N)$ 에 처리 가능하다.

updateTeam()은 최대 100,000번 호출되므로 TLE가 발생한다.

그 다음으로 생각할 수 있는 방법은 병사를 팀별로 묶어서 관리하는 방법이다.

vector<int> team[6]; // 해당 팀에 속한 병사 ID 저장

이렇게 관리하면 updateTeam()은 전체 병사를 순회하지 않고 특정 팀에 속한 병사들에 대해서만 순회하여 수정 가능하다.

단, 한 팀에 병사가 몰리는 경우, 여전히 시간복잡도는 $O(N)$ 을 가지게 된다.

같은 팀 안에서 병사들을 평판 점수별로 나눠 관리하는 방법을 생각할 수 있다. 평판 점수 역시 1 ~ 5 사이 값이므로 다음과 같이 관리할 수 있다.

vector<int> team[6][6]; // team[팀 번호][평판 점수]

updateTeam()에서 어차피 같은 점수를 가진 병사들은 모두 같은 점수로 변경된다. 이전에는 병사 각각의 점수를 갱신했다면, 이번에는 같은 점수의 병사들을 하나의 그룹으로 간주하고 갱신하는 것이다.

다만, 하나의 점수 그룹을 다른 그룹으로 붙이는 과정은 최대 $O(N)$ 이다. 결국 병사들을 다른 점수 그룹으로 일일이 옮겨야 하기 때문이다.

점수 그룹을 옮길 때, 그룹 자체를 이어붙이기 위해 연결 리스트를 생각할 수 있다. 아래 사진을 보면 이해가 쉽다.

hire() 역시 연결 리스트를 사용하면 리스트 뒤에 새로운 병사를 추가하면 되므로 어렵지 않다.

// mTeam의 mScore 리스트 뒤에 새 병사 추가
tail[mTeam][mScore]->next = newNode;
tail[mTeam][mScore] = newNode;

단, 연결 리스트는 각 노드가 다음 노드 정보만 알고 있으므로 fire()에서 병사를 삭제할 때 전체 노드를 순회해야 한다. 삭제 노드 이전 노드의 next를 수정해야 하기 때문이다.

updateSoldier()도 마찬가지이다. 특정 병사를 연결 리스트에서 삭제한 후 다른 연결 리스트에 추가해야 한다.

특정 노드를 찾아 중간에서 제거하려고 한 게 문제라면, 노드를 실제로 삭제하지 않는 방법을 생각할 수 있다. 기존 노드는 리스트에 그대로 두고 유효하지 않은 노드라고 표시하는 것이다.

struct Node {
    int id;
    int version;
    Node* next;
};

int version[100001];

ID가 30인 병사를 고용할 때, 먼저 버전을 올리고 리스트에 삽입한다.

version[30]++;

version의 버전 값과 노드의 버전 값이 일치한다면 해당 노드는 유효한 것이다.

노드 삭제 시에는 물리적으로 삭제하는 것이 아닌, 단순 버전을 올려 무효화한다.

version[30]++;

즉, $O(1)$ 에 fire()을 구현할 수 있다.

updateSoldier() 역시 해당 병사의 버전을 올리고, 새로운 리스트에 유효한 버전과 함께 노드를 추가한다.

bestSoldier() 은 5점부터 리스트를 순회하며 유효한 버전을 가진 노드를 찾으면 된다.

코드

#include <list>
using namespace std;

#define MAX_ID 100000
#define MAX_TEAM 5
#define MAX_SCORE 5

struct Soldier {
    int id;
    int version;
};

// soldierGroup[팀][평판 점수]
list<Soldier> soldierGroup[MAX_TEAM + 1][MAX_SCORE + 1];

// version[id]: 해당 병사의 현재 버전
int version[MAX_ID + 1];

// team[id]: 해당 병사의 소속 팀
int team[MAX_ID + 1];

void init()
{
    // 모든 팀과 점수 그룹 초기화
    for (int t = 1; t <= MAX_TEAM; t++) {
        for (int score = 1; score <= MAX_SCORE; score++) {
            soldierGroup[t][score].clear();
        }
    }

    // 병사별 정보 초기화
    for (int id = 0; id <= MAX_ID; id++) {
        version[id] = 0;
        team[id] = 0;
    }
}

void hire(int mID, int mTeam, int mScore)
{
    // 새로운 상태이므로 버전 증가
    version[mID]++;

    // 해당 팀과 점수 그룹에 병사 추가
    soldierGroup[mTeam][mScore].push_back({mID, version[mID]});

    // 병사의 소속 팀 저장
    team[mID] = mTeam;
}

void fire(int mID)
{
    // 기존 노드는 삭제하지 않고 버전만 변경해 무효화
    version[mID]++;
}

void updateSoldier(int mID, int mScore)
{
    // 기존 노드는 버전이 달라져 무효가 된다.
    version[mID]++;

    // 새로운 점수 그룹에 최신 상태의 노드 추가
    soldierGroup[team[mID]][mScore].push_back({mID, version[mID]});
}

void updateTeam(int mTeam, int mChangeScore)
{
    if (mChangeScore > 0) {
        // 높은 점수부터 처리해야 이미 이동한 그룹을 다시 이동시키지 않는다.
        for (int score = MAX_SCORE; score >= 1; score--) {
            int newScore = score + mChangeScore;

            // 최대 점수는 5
            if (newScore > MAX_SCORE)
                newScore = MAX_SCORE;

            if (score == newScore)
                continue;

            // 현재 점수 그룹 전체를 새로운 점수 그룹 뒤에 연결
            soldierGroup[mTeam][newScore].splice(
                soldierGroup[mTeam][newScore].end(),
                soldierGroup[mTeam][score]
            );
        }
    }
    else if (mChangeScore < 0) {
        // 낮은 점수부터 처리해야 이미 이동한 그룹을 다시 이동시키지 않는다.
        for (int score = 1; score <= MAX_SCORE; score++) {
            int newScore = score + mChangeScore;

            // 최소 점수는 1
            if (newScore < 1)
                newScore = 1;

            if (score == newScore)
                continue;

            // 현재 점수 그룹 전체를 새로운 점수 그룹 뒤에 연결
            soldierGroup[mTeam][newScore].splice(
                soldierGroup[mTeam][newScore].end(),
                soldierGroup[mTeam][score]
            );
        }
    }
}

int bestSoldier(int mTeam)
{
    // 가장 높은 점수부터 확인
    for (int score = MAX_SCORE; score >= 1; score--) {
        int maxID = 0;

        for (const Soldier& soldier : soldierGroup[mTeam][score]) {
            // 현재 버전과 일치하는 노드만 유효한 병사
            if (soldier.version != version[soldier.id])
                continue;

            // 같은 점수라면 ID가 가장 큰 병사를 선택
            if (maxID < soldier.id)
                maxID = soldier.id;
        }

        // 가장 높은 점수 그룹에서 유효한 병사를 찾았으면 반환
        if (maxID != 0)
            return maxID;
    }

    return 0;
}

시간복잡도

bestSoldier()에서 해당 팀의 리스트에 있는 노드를 순회하므로 시간복잡도는 $O(K)$ 이다. 이때 $K$ 는 해당 팀의 리스트에 남아 있는 노드의 수이다. 무효인 노드 포함이다.

init()을 제외한 나머지 메서드들은 전부 $O(1)$ 이다.

공간복잡도

병사의 최대 ID를 $N$ , 노드를 생성하는 메서드는 hire(), updateSoldier()이다. 각각의 호출 횟수를 P, Q라고 하면, 전체 공간복잡도를 $O(N+P+Q)$ 라고 볼 수 있다.