(C++) - 백준(BOJ) 1972번 : 놀라운 문자열 답

www.acmicpc.net/problem/1972

1972번: 놀라운 문자열

 

풀이방법

 1. backtracking 알고리즘을 이용해 조합으로 두 개의 문자를 뽑고 그 때의 거리를 계산해 vector에 저장합니다.

 2. vector의 index가 곧 거리가 되며 해당 거리에 모인 문자열들이 저장되었으니 매 index마다 문자들을 검사하여 map에 없는 문자열이라면 insert해주고 있는 문자열이라면 놀랍지 않으므로 false를 반환해줍니다.

 3. 놀라움의 여부에 따라 적절한 문구를 출력해줍니다.

Code

#include <bits/stdc++.h>
using namespace std;
int check[100];
map<string,int> m;
vector<string> cnt[100];
string word;

bool isSuprising(){
    for(int i =1 ; i <= word.size(); i++){
        m.clear();
        for(int j = 0; j < cnt[i].size(); j++){
            if(m[cnt[i][j]]) return 0;
            else m[cnt[i][j]]++;
        }
    }
    return 1;
}

void backtracking(string word, string w, int idx, int level,int source){
    if(level==2){
        cnt[abs(idx-source)].push_back(w);
        return;
    }
    for(int i = idx; i < word.size(); i++){
        if(!check[i]){
            check[i] = 1;
            backtracking(word,w+word[i],i,level+1,idx);
            check[i] = 0;
        }
    }
}

int main(){
    while(1){
        cin >> word;
        memset(check,0,sizeof(check));
        memset(cnt,0,sizeof(cnt));
        if(word=="*")break;
        backtracking(word,"",0,0,0);
        if(isSuprising()){
            cout << word << " is surprising.\n";
        }else{
            cout << word << " is NOT surprising.\n";
        }
    }
}