3816. [Professional] 아나그램 - D4

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do?courseId=AVuPDj5qAAfw5UW6&subjectId=AWWxo6c6AVkDFAW4&lectureSeq=13&contestProbId=AWH0RjCqB14DFAVB&kataId=#none

SW Expert Academy

이제 슬슬 SW 역량테스트 PRO를 따기 위한 준비를 하고 있습니다.

 

본 문제는 SW 문제해결 심화 강의에서 처음으로 만날 수 있는 문제입니다.

 

아나그램이란 문자열의 문자들을 모두 사용하여 재배열한 것을 의미합니다. ("abc" => "abc", "acb", "bac", "bca", "cab", "cba")

 

위 문제는 S1, S2 문자열 2개가 주어졌을 때(1 <= S1 <= S2 <= 100,000), 과연 S1의 아나그램이 S2에 몇 개가 있는지를 판단하는 문제입니다.

 

아나그램인지 아닌지를 파악하는 방법에서 조금 무식한? 방법으로는 문자열을 전부 재배열 하면서 비교하는 것입니다. 허나 이렇게 해버리면 n개의 문자로 이루어진 단어의 아나그램을 구하기 위해선 최소 n!의 시간이 소모됩니다.

 

그렇기에 앞서 설명한 방법은 좋은 방법이 아닙니다. 그렇다면 다른 방법은 무엇이 있을까요?

 

저희는 문자의 갯수를 중점으로 보아야합니다. 결국 아나그램이란 것이 하나의 문자열을 재배열 했다는 뜻이기에 사용된 문자의 갯수는 항상 일정할 것입니다. 또한, 알파벳의 갯수는 총 26개이기 때문에 이를 이용한다면 충분히 시간 내에 해결할 수 있는 문제가 될 수 있습니다.

 

단, 주의깊게 생각해야할 점이 있습니다. S1의 길이만큼 S2의 단어를 잘라서 그 길이만큼의 알파벳 카운트를 세는 것을 효율적으로 해야합니다.

 

반복문을 돌 때마다 그 길이만큼 카운팅을 다시 초기화하는 방법 보다는, 이미 가지고 있는 카운트에서 앞에 글자를 빼고, 뒤에 글자를 더한다면 O(1)의 시간복잡도로 S2내의 S1 길이만큼의 단어 카운트 배열을 구할 수 있습니다. (이 부분의 이 문제의 키 포인트라 생각합니다)

 

여기까지 구현을 하셨다면, 충분히 해결할 수 있는 문제라고 생각합니다. 지금부터 코드를 보도록 하겠습니다.

 

#include <stdio.h>

int cntCmp(int* arr1, int* arr2) {
	for (int i = 0; i < 26; i++) {
		if (arr1[i] != arr2[i]) return 0;
	}
	return 1;

}

int main(void) {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		char S1[100001], S2[100001];
		scanf("%s %s", S1, S2);
		
		int result = 0;
		int s1CntArr[26] = { 0, };
		int s2CntArr[26] = { 0, };

		int idx = 0;
		while (S1[idx] != '\0') {
			s1CntArr[(int)S1[idx] - 97]++;
			idx++;
		}

		int s2S = 0;
		int s2E = idx;
		for (int i = s2S; i < s2E; i++) { // 처음 시작할 때만 S1 길이만큼의 문자 갯수를 구해봅시다.
			s2CntArr[(int)S2[i] - 97]++;
		}

		if (cntCmp(s1CntArr, s2CntArr)) result++; // 그리고 바로 비교 후 반복문을 시작합니다.
		while (S2[s2E] != '\0') { // 이 부분이 S2 내부의 S1 길이만큼의 문자 갯수를 구하는 곳입니다.
			s2CntArr[(int)S2[s2S] - 97]--;
			s2S++;
			s2E++;
			s2CntArr[(int)S2[s2E - 1] - 97]++;
			if (cntCmp(s1CntArr, s2CntArr)) result++; // 비교하고 맞다면 결과값에 +1을 합니다.
		}
		
		printf("#%d %d\n", t, result);
	}
}

---

이상 3816. [Professional] 아나그램 - D4였습니다. ^_^