글 읽기 - 백준 4195 시간초과 질문드립니다!

yousrain 3년 전 0

제가 생각한 논리대로 문제를 풀어서 제출했으나 시간초과를 받았습니다.

우선 논리를 설명드리면

1) map에 key를 string, value를 int로 정해서 union자료구조를 만든다.

2) 입력받은 두 string를 map의 find로 찾아서 없는 경우 map에 추가한다.

3) 입력받은 두 string을 union하여 출력한다.

입니다.

의심되는 부분은 입력받은 string이 map에 있는지 확인하기 위해 map.find(string)를 썼다는 점인데 정확이 모르겠습니다 ㅠㅠ

부탁드립니다.

#include<stdio.h>
#include<map>
#include<iostream>
using namespace std;
int T, F, uni[200001], cnt[200001];

int Find(int index){
    if(index == uni[index]) return index;
    else return uni[index] = Find(uni[index]);
    return -1;
}

void Union(int x, int y){
    int left = Find(x);
    int right = Find(y);
    if(left != right){
	uni[right] = left;
	cnt[left] += cnt[right];
    }
}

int main(){
    scanf("%d", &T);
    while(T--){
	scanf("%d", &F);
	map<string, int> m;
	int index = 0;
	for(int i = 0; i <= 200000; i++){
	    uni[i] = i;
	    cnt[i] = 0;
	}
	string a, b;
	for(int i = 0; i < F; i++){
	    cin >> a >> b;
	    auto itera = m.find(a);    // a가 맵에 없다면 m.end()를 리턴
	    auto iterb = m.find(b);    // b가 맵에 없다면 ` `
	    auto end = m.end();
	    if(itera != end && iterb != end){    // 둘 다 맵에 있는 경우 합칩합 후 출력
		int left = Find(m[a]);
		int right = Find(m[b]);
		if(left != right){
		    uni[right] = left;
		    cnt[left] += cnt[right];
		    m[b] = left;
		}
		printf("%d\n", cnt[left]);
	    }
	    else if(itera != end && iterb == end){    // a는 있고 b는 없는 경우
		m[b] = index++;
		int left = Find(m[a]);
		int right = Find(m[b]);
		uni[right] = left;
		cnt[left]++;
		m[b] = left;
		printf("%d\n", cnt[left]);
	    }
	    else if(itera == end && iterb != end){    // a는 없고 b는 있는 경우
		m[a] = index++;
		int left = Find(m[a]);
		int right = Find(m[b]);
		uni[left] = right;
		cnt[right]++;
		m[a] = right;
		printf("%d\n", cnt[right]);
	    }
	    else if(itera == end && iterb == end){    // 둘다 없는 경우
		m[a] = index++;
		m[b] = index++;
		int left = Find(m[a]);
		int right = Find(m[b]);
		uni[right] = left;
		cnt[left] = 2;
		m[b] = left;
		printf("%d\n", cnt[left]);
	    }
	}
    }
    return 0;
}

yousrain 3년 전 1

자답입니다. cin하고 scanf차이었습니다.

find함수 사용 시 124ms가 나왔고

count함수 사용 시 128ms 나왔습니다

유의미한 차이는 없는 것 같습니다

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

문제

문제

출처

ICPC

백준 4195 시간초과 질문드립니다!

yousrain 3년 전 0

yousrain 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말