C++ 프로그래머스 Lv5 집합과 쿼리

[C++] 프로그래머스 Lv5 집합과 쿼리

 

2023년 현대모비스 알고리즘 경진대회 예선 문제이다.

본 게시글의 풀이는 58.3점으로 해결하지 못한 문제로 남아있다.

 

문제 설명

정수 0 ~ n-1을 담고 있는 크기가 n인 1차원 정수 배열 a가 있습니다.
배열의 각 원소마다 하나의 집합을 이루고 있습니다.

당신은 여기에 다음 쿼리들을 실행하려고 합니다.

[1, x, y] 형태의 쿼리가 주어집니다.

• y가 포함된 집합의 원소들을 모두 x가 포함된 집합으로 옮깁니다.
• x와 y가 같은 집합에 속해있다면 해당 쿼리는 실행하지 않습니다.

[2, x, y] 형태의 쿼리가 주어집니다.

• 새로운 집합을 생성합니다.
• x와 y가 포함된 집합에서 x와 같거나 늦게 집합으로 들어왔으면서 y와 같거나 빠르게 집합으로 들어온 원소들을 새로 생성한 집합으로 옮깁니다.
• 집합에 들어온 순서는 몇 번째 쿼리로 집합에 들어왔는지로 판별합니다. 같은 쿼리로 집합에 들어왔다면 같은 순서로 집합에 들어왔다는 것을 의미합니다.
• x와 y는 항상 같은 집합에 포함되어 있습니다.

[3, x, y] 형태의 쿼리가 주어집니다.

• x와 y가 같은 집합에 속해있다면 "Yes"를, 그렇지 않다면 "No"를 return 할 배열의 뒤에 추가합니다.

집합은 크기가 0이 되면 사라지며, 초기 집합들은 0번째 쿼리로 형성됩니다.

 

a의 길이를 나타내는 정수 n, 쿼리들을 담은 2차원 정수 배열 queries가 매개변수로 주어집니다. 쿼리들을 순서대로 실행했을 때, 3번 쿼리의 결과를 순서대로 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ n ≤ 500,000
• 1 ≤ queries의 길이 ≤ 500,000
  • queries[i]는 i+1번째로 실행할 쿼리를 나타내며, [q, x, y] 형태의 1차원 정수 배열입니다.
  • 1 ≤ q ≤ 3
  • 0 ≤ x, y < n
  • 2번 쿼리의 경우 x와 y는 항상 같은 집합에 속해 있습니다.
  • 3번 쿼리는 1개 이상 주어집니다.

입출력 예

 

입출력 예 설명

입출력 예 #1

입출력 예 #2

 

문제 풀이

• 먼저 떠오른 것은 링크드 리스트이다.
• 중복되지 않은 숫자들의 집합을 정렬된 상태로 링크를 연결하는 것
• 숫자가 많아졌을 때 조금이라도 넘길 수 있도록 최소 최대값을 비교했다.
• 결과적으로 기본 테스트 케이스는 통과했지만 제출 후 문법과 시간초과를 경험했다.

명령 1

• y가 포함된 집합의 원소들을 모두 x가 포함된 집합으로 옮긴다.
• x와 y가 같은 집합에 속해있다면 해당 쿼리는 실행하지 않는다.
• y의 집합은 모두 쿼리 번호가 업데이트 된다.

명령 2

• x와 y는 항상 같은 집합에 포함되어 있다.
• x의 쿼리 순서는 y의 쿼리 순서보다 항상 작은 것은 아니다.
• x 집합 전체 <= 중간 전체 집합 <= y집합 전체 데이터를 새로운 집합으로 뭉친다.
• 쿼리 번호가 전체적으로 업데이트 된다.
• 링크드 리스트로 구현한 경우 head와 tail을 신경써야 한다.

명령 3

• x와 y가 같은 집합에 포함되어 있는지 확인한다.

 

 

 

 

// 첫 시도

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <algorithm>

using namespace std;

#define MAX_DATA_SIZE 500000

struct SetData
{
    int minData = -1;
    int maxData = -1;
    set<int> datas;
    struct SetData* prevData = nullptr;
    struct SetData* nextData = nullptr;
};


// 대상 값이 들어있는 첫 번째 노드 찾기
SetData* FindSetData(list<SetData*> &setData, int value, bool getTargetNode = false)
{
    list<SetData*>::iterator iter;

    SetData* baseNode = nullptr;    // 첫 번째 집합 노드
    SetData* target = nullptr;       // 순회 노드

    for (iter = setData.begin(); iter != setData.end(); iter++)
    {
        baseNode = *iter;
        target = baseNode;

        while (true)
        {
            // 최소 최대 값으로 한 번 거르기
            if (target->minData <= value && value <= target->maxData)
            {
                // set<int> 안에 값이 들어 있음
                if (target->datas.find(value) != target->datas.end())
                {
                    // 검색 중지
                    // 타겟 노드 필요시 타겟 노드 반환
                    if (getTargetNode)
                        return target;
                    return baseNode;
                }
            }
            if (target->nextData != nullptr)
            {
                target = target->nextData;
            }
            else
            {
                break;
            }
        }
    }
    return nullptr;
}

// 이어 붙일 마지막 노드 찾기
SetData* FindLastNode(SetData* node)
{
    while (node->nextData != nullptr)
    {
        node = node->nextData;
    }
    return node;
}

SetData* CreateNewData(SetData* startNode, SetData* endNode)
{
    SetData* newData = new SetData;

    // 연결이 끊긴 친구들 연결 준비
    SetData* prevNode = startNode->prevData;
    SetData* nextNode = endNode->nextData;

    SetData* node = startNode;
    set<int>::iterator iter;

    while(node != nextNode)
    {
        // y가 포함된 집합 전체를 복사
        for (iter = node->datas.begin(); iter != node->datas.end(); iter++)
        {
            newData->datas.insert(*iter);
        }

        // 다음 노드로 이동
        node = node->nextData;

        // 복사 후 데이터 지우기
        if (node != nullptr)
        {
            delete node->prevData;
            node->prevData = nullptr;
        }
    }

    // 이동 후 나머지가 있다면 연결시켜주기
    if (prevNode != nullptr)
    {
        prevNode->nextData = nextNode;
    }
    if (nextNode != nullptr)
    {
        nextNode->prevData = prevNode;
    }

    newData->minData = *newData->datas.begin();     // 최소 값
    newData->maxData = *newData->datas.rbegin();    // 최대 값

    return newData;
}

void MoveQuery(list<SetData*> &setData, int x, int y)
{
    SetData* xNode = FindSetData(setData, x);   // x의 첫 번째 집합 노드
    SetData* yNode = FindSetData(setData, y);   // y의 첫 번째 집합 노드

    if (xNode != yNode)
    {
        // 연결
        SetData* prevNode = FindLastNode(xNode);
        SetData* nextNode = CreateNewData(yNode, FindLastNode(yNode));

        prevNode->nextData = nextNode;
        nextNode->prevData = prevNode;

        // yNode는 다 옮겼으니 지우기
        setData.remove(yNode);
    }
}

void DivisionQuery(list<SetData*>& setData, int x, int y)
{
    SetData* xNode = FindSetData(setData, x, true);   // x의 집합 노드
    SetData* yNode = FindSetData(setData, y, true);   // y의 집합 노드

    // xNode가 루트노드고 yNode의 다음 노드가 있다면
    if (xNode->prevData == nullptr && yNode->nextData != nullptr)
    {
        setData.remove(xNode);
        setData.push_back(yNode->nextData);
    }

    //SetData* newData = CreateNewData(xNode, yNode);
    setData.push_back(CreateNewData(xNode, yNode));
}

string CheckEqulSet(list<SetData*> &setData, int x, int y)
{
    SetData* dataX = FindSetData(setData, x);
    SetData* dataY = FindSetData(setData, y);

    return dataX == dataY ? "Yes" : "No";
}

void PrintNode(list<SetData*> setData)
{
    list<SetData*>::iterator iter;

    SetData* baseNode = nullptr;    // 첫 번째 집합 노드
    SetData* target = nullptr;       // 순회 노드
    
    int loop = 0;

    for (iter = setData.begin(); iter != setData.end(); iter++)
    {
        baseNode = *iter;
        target = baseNode;

        while (true)
        {
            set<int>::iterator setIter;
            int index = 0;
            for (setIter = target->datas.begin(); setIter != target->datas.end(); setIter++)
            {
                cout << loop << "번째 노드, 인덱스 : " << index++ << ", Value : " << *setIter;
            }
            cout << endl;

            if (target->nextData != nullptr)
            {
                target = target->nextData;
            }
            else
            {
                break;
            }
        }
        loop++;
    }
}


vector<string> solution(int n, vector<vector<int>> queries) {
    vector<string> answer;

    list<SetData*> setDatas;
    
    for (int i = 0; i < n; i++)
    {
        SetData* setData = new SetData;
        setData->minData = i;
        setData->maxData = i;
        setData->datas.insert(i);
        setData->prevData = nullptr;
        setData->nextData = nullptr;
        setDatas.push_back(setData);
    }

    for (int i = 0; i < queries.size(); i++)
    {
        int cmd = queries[i][0];
        int x = queries[i][1];
        int y = queries[i][2];
        cout << i << "번째 쿼리 ---------------" << endl;
        switch (cmd)
        {
            case 1 :
                MoveQuery(setDatas, x, y);
                break;
            case 2 :
                DivisionQuery(setDatas, x, y);
                break;
            case 3 :
                answer.push_back(CheckEqulSet(setDatas, x, y));
                break;
        }
        PrintNode(setDatas);

    }
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << ", ";
    }

    return answer;
}

int main()
{
    vector<vector<int>> q;
    //q.push_back({ 3, 2, 3 });
    //q.push_back({ 1, 3, 2 });
    //q.push_back({ 3, 2, 3 });
    //q.push_back({ 1, 2, 0 });
    //q.push_back({ 3, 0, 1 });
    //q.push_back({ 2, 2, 0 });
    //q.push_back({ 3, 2, 3 });
    //q.push_back({ 3, 0, 2 });
    //solution(4, q);

    q.push_back({ 1, 0, 1 });
    q.push_back({ 1, 2, 3 });
    q.push_back({ 3, 1, 3 });
    q.push_back({ 1, 2, 0 });
    q.push_back({ 3, 1, 3 });
    q.push_back({ 1, 1, 5 });
    q.push_back({ 1, 5, 4 });
    q.push_back({ 3, 4, 5 });
    q.push_back({ 2, 2, 5 });
    q.push_back({ 3, 4, 5 });
    solution(7, q);
}

 

 

// 두 번째 시도	13 / 27
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_DATA_SIZE 500000

struct SetData
{
    int queryIndex = 0;
    SetData* prevNode = nullptr;
    SetData* nextNode = nullptr;
    SetData* lastNode = nullptr;
    int number;
};

int baseData[MAX_DATA_SIZE];    // 베이스 노드의 인덱스를 가리키는 데이터
int queryData[MAX_DATA_SIZE]{ 0, };   // 해당 번호가 몇 번째 쿼리로 이동되었는지 기록하는 데이터
SetData* setDatas[MAX_DATA_SIZE];
SetData* selfData[MAX_DATA_SIZE];


// 해당 노드의 마지막 노드를 반환합니다.
SetData* FindLastNode(SetData* setData)
{
    return setData->lastNode;
}

// 시작 노드 부터 마지막 노드 까지 쿼리 인덱스, 베이스 인덱스를 바꿔줍니다.
void ChangeNodeIndex(SetData* setData, int baseIndex, int queryIndex = -1)
{
    SetData* node = setData;
    do
    {
        if(queryIndex >= 0)
        {
            node->queryIndex = queryIndex;          // 쿼리 인덱스
            queryData[node->number] = queryIndex;   // 쿼리 인덱스
        }
        baseData[node->number] = baseIndex;     // 베이스 노드 인덱스

        node = node->nextNode;
    } while (node != nullptr);
}

void MoveSetData(int index, int x, int y)
{
    int destIndex = baseData[x];     // x의 베이스 노드
    int targetIndex = baseData[y];   // y의 베이스 노드

    SetData* lastNode = FindLastNode(setDatas[destIndex]);
    SetData* targetNode = setDatas[targetIndex];

    setDatas[destIndex]->lastNode = targetNode->lastNode;

    lastNode->nextNode = targetNode;
    targetNode->prevNode = lastNode;
    
    // 비워진 배열의 주소값은 지워주기
    setDatas[targetIndex] = nullptr;

    ChangeNodeIndex(targetNode, destIndex, index);
}

SetData* FindQueryLastNode(SetData* setData, int queryIndex)
{
    SetData* node = setData;
    do
    {
        // 현재 쿼리인덱스가 같고 다음 노드가 nullptr이거나 queryIndex가 다른 경우
        if (node->queryIndex == queryIndex)
            if (node->nextNode == nullptr || node->nextNode->queryIndex != queryIndex)
                break;

        node = node->nextNode;
    } while (node != nullptr);

    return node;
}

SetData* FindStartNode(SetData* setData, int queryIndex)
{
    SetData* node = setData;
    do
    {
        if (node->queryIndex == queryIndex)
            if (node->prevNode == nullptr || node->prevNode->queryIndex != queryIndex)
                break;

        node = node->prevNode;
    } while (node != nullptr);
    return node;
}

void DivisionSetData(int index, int x, int y)
{
    int xQueryIndex = queryData[x];
    int yQueryIndex = queryData[y];
    // query : x <= data <= y
    if (xQueryIndex > yQueryIndex)
        return;

    int baseIndex = baseData[x];     // x의 베이스 노드

    SetData* baseNode = setDatas[baseIndex];

    // x와 같은 쿼리 인덱스를 가진 시작 노드를 찾는다.
    // y와 같은 쿼리 인덱스를 가진 끝 노드를 찾는다.
    SetData* startNode = FindStartNode(selfData[x], xQueryIndex);
    SetData* lastNode = FindQueryLastNode(selfData[y], yQueryIndex);

    // base노드와 시작 노드가 같다면
    if (baseNode->number == startNode->number)
    {
        if (lastNode->nextNode != nullptr)
        {
            //  - 끝 노드 다음 노드가 있다면 대표값을 변경하고 자리를 옮겨준다.
            SetData* nextData = lastNode->nextNode;
            int targetIndex = nextData->number;
            setDatas[targetIndex] = nextData;
            nextData->lastNode = baseNode->lastNode;

            nextData->prevNode = nullptr;
            startNode->prevNode = nullptr;
            lastNode->nextNode = nullptr;
            // 베이스를 바꿔준다.
            ChangeNodeIndex(nextData, targetIndex);
        }
    }
    else
    {
        // base노드와 시작 노드가 같지 않다면
        //  - end노드의 다음이 있는지 검사한 후
        //  - startNode의 이전 노드와 연결해 준다.
        startNode->prevNode->nextNode = nullptr;
        if (lastNode->nextNode != nullptr)
        {
            startNode->prevNode->nextNode = lastNode->nextNode;
            lastNode->nextNode->prevNode = startNode->prevNode;
        }
        else
        {
            baseNode->lastNode = startNode->prevNode;
        }
        startNode->prevNode = nullptr;
        lastNode->nextNode = nullptr;
    }

    startNode->lastNode = lastNode;

    int targetIndex = startNode->number;
    setDatas[targetIndex] = startNode;
    ChangeNodeIndex(startNode, targetIndex, index);
}

string CheckEqulSetData(int x, int y)
{
    int xIndex = baseData[x];
    int yIndex = baseData[y];

    return xIndex == yIndex ? "Yes" : "No";
}

void DebugPrint(int n)
{
    SetData* data;
    for (int i = 0; i < n; i++)
    {
        if (setDatas[i] != nullptr)
        {
            cout << i << "번째 값 : " << endl;
            data = setDatas[i];
            do
            {
                cout << data->number << ", ";
                data = data->nextNode;

            } while (data != nullptr);
        }
        cout << endl;
    }
}

vector<string> solution(int n, vector<vector<int>> queries) {
    vector<string> answer;

    for (int i = 0; i < n; i++)
    {
        SetData* data = new SetData;
        data->number = i;
        data->lastNode = data;

        setDatas[i] = data;

        selfData[i] = data;

        baseData[i] = i;
    }

    for (int i = 0; i < queries.size(); i++)
    {
        int cmd = queries[i][0];
        int x = queries[i][1];
        int y = queries[i][2];
        
        cout << i << "번째 질의, x 값 : " << x << ", y값 : " << y << endl;

        if (cmd == 1)
        {
            MoveSetData(i, x, y);

        }
        else if (cmd == 2)
        {
            DivisionSetData(i, x, y);
        }
        else if (cmd == 3)
        {
            answer.push_back(CheckEqulSetData(x, y));
        }
        DebugPrint(n);
    }

    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << ", ";
    }

    return answer;
}

// 시간 복잡도를 조금 개선한 풀이

#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define MAX_DATA_SIZE 500000

struct SetData
{
    int number;
    int queryIndex = 0;
    bool isGroupStartNode = true;
    SetData* baseNode = nullptr;
    SetData* prevNode = nullptr;
    SetData* nextNode = nullptr;
    SetData* lastNode = nullptr;
    SetData* groupLastNode = nullptr;
};

SetData* selfData[MAX_DATA_SIZE];


SetData* GetStartNode(SetData* setData)
{
    SetData* node = setData;
    do
    {
        if (node->isGroupStartNode)
            break;

        node = node->prevNode;
    } while (node != nullptr);
    return node;
}

SetData* GetLastNode(SetData* setData)
{
    return GetStartNode(setData)->groupLastNode;
}

SetData* GetBaseNode(SetData* setData)
{
    return GetStartNode(setData)->baseNode;
}

void InitializeOtherNode(SetData* setData, SetData* baseNode, int index)
{
    SetData* node = setData;
    setData->queryIndex = index;
    setData->isGroupStartNode = true;
    setData->baseNode = baseNode;
    do
    {
        node = node->groupLastNode->nextNode;
        if (node == nullptr)
            break;
        node->isGroupStartNode = false;
        node->baseNode = nullptr;
        node->lastNode = nullptr;
    } while (true);
    setData->groupLastNode = setData->lastNode;
    setData->lastNode = nullptr;
}

void ChangeBaseNode(SetData* setData, SetData* baseNode)
{
    SetData* node = setData;
    do
    {
        node = node->groupLastNode->nextNode;
        if (node == nullptr)
            break;
        node->baseNode = baseNode;
    } while (true);
}

void MoveSetData(int index, int x, int y)
{
    SetData* baseNode = GetBaseNode(selfData[x]);
    SetData* lastNode = baseNode->lastNode;
    SetData* targetNode = GetBaseNode(selfData[y]);

    InitializeOtherNode(targetNode, baseNode, index);
    baseNode->lastNode = targetNode->groupLastNode;

    lastNode->nextNode = targetNode;
    targetNode->prevNode = lastNode;
}

void DivisionSetData(int index, int x, int y)
{
    SetData* startNode = GetStartNode(selfData[x]);
    SetData* lastNode = GetLastNode(selfData[y]);
    SetData* baseNode = startNode->baseNode;

    if (startNode->queryIndex > lastNode->queryIndex)
        return;

    if (baseNode->number == startNode->number)
    {
        if (lastNode->nextNode != nullptr)
        {
            SetData* nextData = lastNode->nextNode;
            nextData->lastNode = baseNode->lastNode;
            nextData->baseNode = nextData;
            ChangeBaseNode(nextData, nextData);

            nextData->prevNode = nullptr;
        }
    }
    else
    {
        startNode->prevNode->nextNode = nullptr;
        if (lastNode->nextNode != nullptr)
        {
            startNode->prevNode->nextNode = lastNode->nextNode;
            lastNode->nextNode->prevNode = startNode->prevNode;
        }
        else
        {
            baseNode->lastNode = startNode->prevNode;
        }
    }
    startNode->prevNode = nullptr;
    lastNode->nextNode = nullptr;

    InitializeOtherNode(startNode, startNode, index);
    startNode->groupLastNode = lastNode;
    startNode->lastNode = lastNode;

}

string CheckEqulSetData(int x, int y)
{
    int xIndex = GetBaseNode(selfData[x])->number;
    int yIndex = GetBaseNode(selfData[y])->number;

    return xIndex == yIndex ? "Yes" : "No";
}

vector<string> solution(int n, vector<vector<int>> queries) {
    vector<string> answer;

    for (int i = 0; i < n; i++)
    {
        SetData* data = new SetData;
        data->number = i;
        data->baseNode = data;
        data->lastNode = data;
        data->groupLastNode = data;

        selfData[i] = data;
    }

    for (int i = 0; i < queries.size(); i++)
    {
        int cmd = queries[i][0];
        int x = queries[i][1];
        int y = queries[i][2];

        switch (cmd)
        {
            case 1 :
                MoveSetData(i, x, y);
                break;
            case 2 :
                DivisionSetData(i, x, y);
                break;
            case 3 :
                answer.push_back(CheckEqulSetData(x, y));
                break;
        }
    }

    return answer;
}