[백준/BOJ] 백준 24431번 : 유사 라임 게임

https://www.acmicpc.net/problem/24431

24431번: 유사 라임 게임

 

각 단어의 길이 f인 접미사를 추출하여, 해당 접미사가 몇 개 나왔는지 세는 방법을 통해 유사 라임 쌍을 구해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;

int t;
vector<int> output;

int n, l, f;
vector<string> words;
map<string, int> check; //(접미사, 해당 접미사가 나온 횟수)

void init() {
	words.clear();
	check.clear();
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> t;

	for (int tc = 0; tc < t; tc++) {

		init();
		cin >> n >> l >> f;

		for (int i = 0; i < n; i++) {
			string input;
			cin >> input;

			words.push_back(input);
		}

		for (int i = 0; i < words.size(); i++) {
			string check_word = words[i].substr(l - f, f); //접미사 추출

			if (check.count(check_word) == 0) {
				check.insert(make_pair(check_word, 1));
			}

			else {
				check[check_word]++;
			}

		}

		int result = 0;
		for (map<string, int>::iterator it = check.begin(); it != check.end(); it++) {
			int check_word_count = (*it).second;
			result += (check_word_count / 2); //check_word_count개의 유사 라임으로 만들 수 있는 유사 라임 쌍의 개수
		}

		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i] << "\n";
	}

	return 0;
}