취미로 코딩하기

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

이번에 볼 문제는 백준 6443번 문제인 애너그램이다.

문제는 아래 링크를 확인하자.

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

입력으로 영단어가 주어질 때 이 영단어를 구성하는 알파벳을 순서만을 바꿔 만들 수 있는 문자열들을 한 번씩 사전순으로 출력하는 문제이다.

주어진 단어를 구성하는 알파벳의 종류와 그 등장 횟수를 기록하고, 이를 이용해 모든 순열을 사전순으로 탐색하는 것으로 문제를 해결할 수 있다.

문자열을 정렬하면 알파벳의 종류와 등장 횟수를 찾아내는 구현을 간단히 할 수 있다.

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

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

int lettercnt, slen;
char c[20];
int cnt[20];
string s = "";

void func(int len) {
	if (len == slen) {
		cout << s << '\n';
		return;
	}

	for (int i = 0; i < lettercnt; i++) {
		if (cnt[i]) {
			cnt[i]--;
			s += c[i];
			func(len + 1);
			s.pop_back();
			cnt[i]++;
		}
	}
}

void solve() {
	string tmp; cin >> tmp;
	sort(tmp.begin(), tmp.end());

	lettercnt = -1, slen = tmp.length();
	char old = '\\';
	for (auto l : tmp) {
		if (l != old) {
			old = l;
			lettercnt++;
			c[lettercnt] = l;
			cnt[lettercnt] = 0;
		}
		cnt[lettercnt]++;
	}
	lettercnt++;

	func(0);
}

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

	int T; cin >> T;
	while (T--) {
		solve();
	}
}