취미로 코딩하기

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

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

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

주어지는 두 문자열의 문자의 순서는 중요하지 않으므로 문자열 대신 각 문자열을 구성하는 알파벳의 개수의 배열을 관리해주자.

알파벳을 다른 알파벳으로 바꾸는 것을 "다음 문자로 바꾸는 단위 작업"을 반복하는 것으로 생각할 때, 최적의 연산방법은 A를 B로, B를 C로, ..., Y를 Z로, Z를 A로 바꾸는 모든 26가지 연산이 포함되어 있을 수는 없음을 관찰하자. 이러한 작업이 모두 있다면 이 모든 작업을 전부 한 번씩 덜 하는 것으로 더 적은 연산횟수로 문제를 해결할 수 있게 되기 때문이다.

위의 관찰을 토대로, 최적의 연산방법의 경우 적어도 어느 한 문자는 다음 문자로의 변환을 하지 않음을 알 수 있다. 이를 이용해 문자의 변환을 원형리스트와 같이 하는 것이 아닌 "변환을 하지 않을 두 문자의 사이"를 끊어 얻을 수 있는 26가지 후보 각각의 배열과 같이 시도해 문제를 해결할 수 있게 된다.

각 구분된 배열에 대한 최소 횟수는 그리디한 방법을 이용해 변환이 가능하다면 그 최소횟수를, 불가능하다면 가능하지 않음을 아래와 같은 구현으로 간단히 구해낼 수 있다.

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

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

string s1, s2;
int arr[52];
int ans = 1000000007;

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

	cin >> s1 >> s2;
	for (auto& l : s1) arr[l - 'A']++;
	for (auto& l : s2) arr[l - 'A']--;

	for (int i = 0; i < 26; i++) arr[i + 26] = arr[i];

	for (int L = 0; L < 26; L++) {
		int R = L + 26;
		bool chk = 1;
		int tmp = 0;
		int val = 0;
		for (int i = L; i < R; i++) {
			val += tmp;
			tmp += arr[i];
			if (tmp < 0) chk = 0;
		}
		if (chk) ans = min(ans, val);
	}

	cout << ans;
}