텍스트 스트림과 하나의 단어가 입력으로 주어졌을 때, 주어진 텍스트 안에서 해당 단어의 아나그램이 몇 번 등장하는지 찾아내는 것이 이번 문제의 목표입니다. 아나그램(anagram)은 단어를 구성하는 글자들을 재배열하여 만들어진 다른 단어나 문구를 의미합니다. 예를 들어 "New York Times"의 글자들을 재배열하면 "Monkeys write"라는 문구를 만들 수 있습니다.
예시
입력: 문자열 string-: "workitwrokoffowkr", word = "work"
출력: 문자열 내 아나그램 출현 횟수: 3
설명: "work"로 만들 수 있는 아나그램에는 work, wrok, rowk, owkr 등이 있습니다. 주어진 문자열에는 work, wrok, owkr 세 개의 아나그램이 존재하므로 결과는 3입니다.
입력: 문자열 string-: "expresshycool", word = "Zen"
출력: 문자열 내 아나그램 출현 횟수: 0
설명: "zen"으로 만들 수 있는 아나그램에는 nez, ezn, enz, zne, nze, zen 등이 있습니다. 주어진 문자열에는 "zen"의 아나그램이 존재하지 않으므로 결과는 0입니다.
프로그램에 적용된 접근 방식
- 문자열(stream)과 단어(w)를 함수 countAna(stream, w)에 전달하여 처리합니다.
- 함수(countAna) 내부에서 카운트 변수를 초기화합니다.
- i = 0부터 i <= (stream.length()) - (w.length())까지 FOR 루프를 실행합니다.
- 루프 내부에서 arrangeAna(w, stream.substring(i, i + w.length())) 함수를 호출합니다. 이때 스트림에서 단어와 같은 길이의 부분 문자열을 잘라 전달합니다.
- arrangeAna 함수 내부에서는 두 문자열을 각각 문자 배열로 변환한 뒤 정렬합니다.
- 정렬된 두 배열이 동일한지 비교하여(즉, 두 문자열이 아나그램 관계인지 확인) 그 결과(true/false)를 반환합니다.
- 반환값이 true이면 countAna() 내부의 카운트 값을 증가시킵니다.
- 최종 결과는 main() 메서드에서 받아 출력됩니다.
예제 코드
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
// 두 문자열이 아나그램 관계인지 확인하는 함수
static bool arrangeAna(string s1, string s2) {
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
return s1 == s2;
}
// 스트림에서 단어의 아나그램 출현 횟수를 세는 함수
static int countAna(string stream, string w) {
int count = 0;
for (int i = 0; i <= (int)(stream.length()) - (int)(w.length()); i++) {
if (arrangeAna(w, stream.substr(i, w.length()))) {
count++;
}
}
return count;
}
int main() {
string stream = "workitwrokoffowkr";
string w = "work";
cout << "Count of occurrences of anagram in the string are: "
<< countAna(stream, w) << endl;
return 0;
}
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
출력
Count of occurrences of anagram in the string are: 3