문제 개요
이 문제에서는 하나의 문자열이 주어지며, 출현 빈도가 소수(Prime Number)인 문자들의 빈도값을 모두 XOR 연산한 결과를 출력하는 것이 목표입니다.
예시를 통해 문제를 살펴보겠습니다.
- 입력 − tutorialspoint
- 출력 − 3
"tutorialspoint"라는 문자열에서 각 문자의 출현 횟수를 세어 보면 다음과 같습니다.
- t는 3번, o는 2번, i는 2번 나타납니다.
- 나머지 문자(u, r, a, l, s, p, n)는 모두 1번씩만 나타납니다.
여기서 빈도가 소수인 문자는 t(3), o(2), i(2)입니다. 따라서 XOR 연산 결과는 3 ^ 2 ^ 2 = 3이 됩니다.
접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 소수 판별 배열 준비 − 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 미리 소수 여부를 저장한 배열을 만듭니다.
- 문자 빈도 계산 − 맵(map) 자료구조를 사용해 문자열의 각 문자별 출현 빈도를 저장합니다.
- XOR 연산 수행 − 맵을 순회하며 각 문자의 빈도가 소수인지 확인하고, 소수라면 결과값에 해당 빈도를 XOR 연산합니다.
- 예외 처리 − 빈도가 소수인 문자가 하나도 존재하지 않으면 -1을 반환합니다.
구현 예제
위 접근 방식을 C++로 구현한 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
// 에라토스테네스의 체로 소수 판별 배열 생성
void findPrimes(bool prime[], int p_size){
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= p_size; p++) {
if (prime[p]) {
for (int i = p * 2; i <= p_size; i += p)
prime[i] = false;
}
}
}
// 소수 빈도를 가진 문자들의 빈도 XOR 계산
int findPrimeXOR(string s){
bool prime[100005];
memset(prime, true, sizeof(prime));
findPrimes(prime, 10005);
int i, j;
map<char, int> charFreq;
for (i = 0; i < s.length(); i++)
charFreq[s[i]]++;
int result = 0;
int flag = 0;
for (auto i = charFreq.begin(); i != charFreq.end(); i++) {
if (prime[i->second]) {
result = result ^ i->second;
flag = 1;
}
}
if (!flag)
return -1;
return result;
}
int main(){
string s = "tutorialspoint";
cout<<"The XOR of frequencies of character which have prime frequencies is : ";
cout<<findPrimeXOR(s);
return 0;
}실행 결과
The XOR of frequencies of character which have prime frequencies is : 3
코드 설명
findPrimes() 함수는 에라토스테네스의 체 알고리즘을 사용하여 인덱스 값이 소수인 위치에 true를 저장하는 배열을 생성합니다. 이 방식의 시간 복잡도는 O(N log log N)으로 매우 효율적입니다.
findPrimeXOR() 함수는 먼저 맵에 각 문자의 빈도를 기록한 뒤, 맵을 순회하면서 빈도가 소수인 문자의 빈도값만 XOR 연산에 누적합니다. 플래그 변수(flag)를 통해 조건을 만족하는 문자가 존재했는지 추적하며, 하나도 없었다면 -1을 반환합니다.
전체 알고리즘의 시간 복잡도는 O(N)이며, 여기서 N은 문자열의 길이입니다.