백준 1972 놀라운 문자열 - substr로 해결못하는 문자열 처리 문제

문제 링크

https://www.acmicpc.net/problem/1972

1972번: 놀라운 문자열

종강 기념으로 다시 알고리즘 시작한다! 길고 긴 학기였다...

해결 아이디어

문자열 처리 문제이다.

각 case에 대해 1부터 len-1 까지, 처음부터 끝까지 검사하고 ,

set를 이용해 하나도 겹치지 않고 나오는지 개수를 파악해서 검사했다.

총 n^3의 시간복잡도가 사용되겠지만 case수가 100개가 최대이므로 시간내에 돌아간다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    string s;
    bool it = true;
    while(it){
        cin>>s;
        if(s=="*"){
            it=false;
            break;
        }
        int len = s.length();
        bool flag = true;
        for(int i=1; i<=(len-1); i++){
            set<string> sett;
            for(int j=0; j<=len-i-1; j++){
                string b;
                b.push_back(s[j]);
                b.push_back(s[j+i]);
                sett.insert(b);
            }
            if(sett.size()!=len-i) flag=false;
            if(!flag){
                break;
            }
        }
        if(!flag) cout<<s<<" is NOT surprising.\n";
        else cout<<s<<" is surprising.\n";
    }
}