[BOJ] 1972. 놀라운 문자열 (C++)

• 코딩 초보

---

1972. 놀라운 문자열 (실버3) 

 

대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문자열의 D-쌍이라고 한다. 예를 들어 문자열이 ZGBG라고 하자. 이 문자열의 0-쌍은 ZG, GB, BG가 되고, 이 문자열의 1-쌍은 ZB, GG가 되며, 이 문자열의 2-쌍은 ZG가 된다. 문자열의 길이가 N이라고 할 때, 0-쌍부터 (N-2)-쌍까지가 정의됨을 알 수 있다.

만일 정의되는 D에 대해, 어떤 문자열의 모든 D-쌍들이 서로 다를 때, 이 문자열을 D-유일하다고 한다. 위의 예를 보면, 0-쌍들은 ZG, GB, BG로 모두 다르다. 따라서 이 문자열은 0-유일하며, 마찬가지로 1-유일하고, 2-유일하다. 하지만 만일 문자열이 AAA라고 하자. 이 문자열은 0-유일하지 않으며, 다만 1-유일하다.

만일 어떤 문자열이 정의되는 모든 D에 대해 D-유일하면, 이 문자열을 정말이지 ‘놀라운 문자열’이라고 한다. 문자열이 주어질 때, 이 문자열이 놀라운 문자열인지 아닌지를 구하는 프로그램을 작성하시오.

 

 

입력의 각 줄에는 알파벳 대문자로만 구성된 문자열이 주어진다. 모든 문자열의 길이는 80을 넘지 않으며, 입력의 마지막 줄에는 마지막을 나타내는 *가 주어진다. 입력은 마지막 줄을 포함해서 101줄을 넘지 않는다.

 

각 줄에 이 문자열이 놀라운(surprising) 문자열인지 아닌지를 아래의 예제와 같이 출력한다.

 

---

#include <iostream> 
#include <string>
#include <unordered_set>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    string s;

    
    while (true) {
        cin >> s;
        if (s == "*") break;
        int isSurprise = 0; 
        for (int i = 1; i <= s.length() - 1; i++) {
            unordered_set<string> v;
            for (int j = 0; j < s.length() - i; j++) {
                string temp;
                temp += s[j];
                temp += s[j + i]; 
                if (v.count(temp) == 0) v.insert(temp);
                else isSurprise++; 
            }   
        }
        if (isSurprise == 0) cout << s << " is surprising.\n";
        else cout << s << " is NOT surprising.\n";
    }
    return 0; 

}

isSurprise가 한번도 증가하지 않고 0을 그대로 유지한다면 놀라운 문자열이고, 한번이라도 증가하게된다면 놀라운 문자열이 아니다. 

v라는 배열을 따로 만들어주어서 각 쌍들을 탐색할때 v.count에서 하나라도 찾게 되면 isSurprise를 증가시키도록 했다.