[C++] 백준 1972번:놀라운 문자열

문제링크

1972번: 놀라운 문자열

문제

대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘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) 문자열인지 아닌지를 아래의 예제와 같이 출력한다.

 

풀이

D-쌍의 단어를 입력 받은 단어의 앞부터 만들면서 배열에 저장해준다. 이 때 배열에 같은 단어가 존재하면 해당 문자열은 놀라운 단어가 아니기 때문에 "is NOT surprising."을 출력해준다.

만약 모든 D(0 ~ N-2)에 대해 유일하다면 "is surprising."을 출력해준다.

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
string str;
 
// 배열이 str을 포함하는지 여부를 알아내는 함수
bool sub(vector<string> v, string str) {
    for (auto e : v) {
        if (e == str) {
            return true;
        }
    }
    return false;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    while (true) {
        cin >> str;
        bool possible = true;    // 불가능 flag
 
        // "*"이면 종료
        if (str == "*") {
            return 0;
        }
 
        int size = str.size();
        int num = 1;    // (i-1)쌍
 
        while (num <= size - 1) {
 
            vector<string> v;    // num-1 쌍 단어 저장 벡터
 
            for (int i = 0; i < size - num; i++) {
                // num-1 쌍 단어 만들어서 저장
                string tmp = to_string(str[i]) + to_string(str[i+num]);
                
                // 같은 단어가 있다면 불가능
                if (sub(v, tmp) == true) {
                    possible = false;
                    break;
                }
                v.push_back(tmp);
            }
 
            // 불가능하면 break -> 속도를 줄이기 위함
            // 있으면 0ms 없으면 32ms가 걸린다.
            if (possible == false) {
                break;
            }
 
            // 쌍 크기 증가
            num++;
        }
 
        if (possible == false) {
            cout << str << " is NOT surprising." << '\n';
        }
        else {
            cout << str << " is surprising." << '\n';
        }
    }
 }

 

메모

53번 라인, 54번 라인은 시간 단축을 위한 코드이다. 해당 코드를 제외하고 제출하면 32ms가 걸리고 포함하고 제출하면 0ms가 걸린다.