문제
문자열이 "놀라운(surprising)" 문자열인지 판별하라. 모든 거리 D에 대해 D-쌍(거리 D만큼 떨어진 두 문자 조합)이 모두 고유하면 놀라운 문자열이다.
입력
여러 줄에 문자열이 주어지며, *이면 종료한다.
출력
각 문자열에 대해 {문자열} is surprising. 또는 {문자열} is NOT surprising.을 출력한다.
예제
| 입력 | 출력 |
|---|---|
ZGBG X EE * | ZGBG is surprising. X is surprising. EE is NOT surprising. |
풀이
모든 거리 D에 대해 D-쌍의 중복 여부를 HashSet으로 검사한다.
- 거리 D를 0부터 문자열 길이-2까지 순회한다
- 각 D에 대해 모든 위치 i에서
(s[i], s[i+D+1])쌍을 만든다 - 이 쌍이 이미 Set에 있으면 놀라운 문자열이 아니다
- 모든 D에서 중복이 없으면 놀라운 문자열이다
핵심 아이디어: D-쌍은 거리별로 독립적이므로, 각 거리마다 Set을 초기화하여 중복을 확인한다.
코드
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isSurprising(const string &s)
{
int n = s.length();
for (int d = 0; d < n - 1; ++d)
{
unordered_set<string> seen;
for (int i = 0; i + d + 1 < n; ++i)
{
string pair;
pair += s[i];
pair += s[i + d + 1];
if (seen.count(pair))
{
return false; // 중복된 D-쌍 발견 → surprising 아님
}
seen.insert(pair);
}
}
return true;
}
int main()
{
string s;
while (getline(cin, s))
{
if (s == "*")
break;
if (isSurprising(s))
{
cout << s << " is surprising." << endl;
}
else
{
cout << s << " is NOT surprising." << endl;
}
}
return 0;
}복잡도
- 시간: O(N²) — 거리 D마다 최대 N개 쌍 검사
- 공간: O(N) — 각 거리별 HashSet