BOJ - 14425 문자열 집합 해결 전략 (C++)

• 문제 링크
  백준 14425번 - 문자열 집합

해결 전략

  본 문제를 보자마자 우리는 Search의 대상과 Search의 주체가 모두 10,000개이기 때문에, 문자열 비교까지 고려하면 시간 제한 내에 Naive한 방식으로는 해결할 수 없음을 어렵지 않게 알 수 있다.

  이럴 때는, 아래와 같은 간단한 Trick을 적용해 해결책을 모색할 수 있다.

Naive하게 Search하되, 대상의 범위를 좁히자.

예를 들면, 문자열 길이, 문자열 첫 글자, 문자열 맨 뒷 글자라는 세 지표를 기준으로 자료구조를 구분하는 것이다.

~> 바로 이해할 수 있을 것이다.

  아래는 정답 코드이다.

#include <iostream>
#include <vector>
#include <string>
// BOJ 14425 Set of strings
#define get_temp() string temp; cin >> temp;
#define len temp.length()
#define first temp.front()-97
#define last temp.back()-97
using namespace std;

vector<string> str[501][26][26];

int main(void) {
	int n, m, cnt = 0;
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		get_temp();
		str[len][first][last].push_back(temp);
	}

	for (int i = 0; i < m; i++) {
		get_temp();
		for (int j = 0; j < str[len][first][last].size(); j++)
			if (temp.compare(str[len][first][last][j]) == 0)
				cnt++;
	}
	cout << cnt;

	return 0;
}

~> 유사한 원리로 백준 1620번 - 나는야 포켓몬 마스터 이다솜, 백준 1764번 - 듣보잡도 쉽게 해결할 수 있다.