취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7587번 문제인 Anagrams다.
문제는 아래 링크를 확인하자.

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

어떤 두 문자열이 anagram인 관계라면 각 문자열을 구성하는 문자들을 알파벳순으로 정렬했을 때 얻을 수 있는 두 문자열이 같고, 그 역 또한 성립함을 관찰하자.

이를 이용하면 각 문자열을 구성하는 문자들을 정렬해 얻은 문자열을 이용해 두 문자열이 anagram인 관계를 확인하는 것이 가능하다.

map을 이용해 문자가 정렬된 문자열 별로 가장 먼저 등장한 원본 문자열이 무엇인지, 그리고 그러한 문자열이 몇 개 등장했는지 관리해 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int N;
map<string, int> mpidx;
int cnt[1000]; string mpstr[1000];

void solve() {
	mpidx.clear();
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		string ss = s;
		sort(s.begin(), s.end());
		if (mpidx.count(s)) cnt[mpidx[s]]++;
		else {
			mpidx[s] = i;
			cnt[i] = 1, mpstr[i] = ss;
		}
	}
	int mx = 0, ansid;
	for (int i = 0; i < N; i++) {
		if (cnt[i] > mx) mx = cnt[i], ansid = i;
	}
	cout << mpstr[ansid] << ' ' << mx - 1 << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N) {
		solve();
		cin >> N;
	}
}