글 읽기 - 4195 map으로 string을 int 처리하였지만 시간초과가 납니다.

dohyung97022 3년 전 0

map을 두개씩이나 사용해서 이러는 것일까요?

array가 map보다 빠른 구조라서 틀리는 것 같다는 생각이 들기도 합니다...

// 시간초과

// string map의 경우 string을 index 처리하여 사용하자.
// 있는 것에서 수정하자.

#include <iostream>
#include <map>
using namespace std;

// union find
// map<Int has the root of pair<Int, and the size of Int>>
map<int, pair<int, int>> rootMap;

int find(int friendA)
{
    if (rootMap[friendA].second == 0)
    {
        rootMap[friendA].first = friendA;
        rootMap[friendA].second = 1;
    }
    if (rootMap[friendA].first == friendA)
        return friendA;
    else
        return find(rootMap[friendA].first);
}

void unionn(int friendA, int friendB)
{
    friendA = find(friendA);
    friendB = find(friendB);
    if (friendA != friendB)
    {
        rootMap[friendA].first = friendB;
        rootMap[friendA].second += rootMap[friendB].second;
        rootMap[friendB].second = rootMap[friendA].second;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int testCase;
    cin >> testCase;
    while (testCase--)
    {
        int relationCount, idxCount = 0;
        cin >> relationCount;
        map<string, int> nameIdx;
        while (relationCount--)
        {
            string friendA, friendB;
            cin >> friendA >> friendB;
            if (nameIdx[friendA] == 0)
                nameIdx[friendA] = idxCount++;
            if (nameIdx[friendB] == 0)
                nameIdx[friendB] = idxCount++;
            unionn(nameIdx[friendA], nameIdx[friendB]);
            cout << rootMap[nameIdx[friendA]].second << "\n";
        }
        rootMap.clear();
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4195 map으로 string을 int 처리하였지만 시간초과가 납니다.

dohyung97022 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말