[백준OJ] 9933번 민균이의 비밀번호

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

9933번: 민균이의 비밀번호

---

 

-풀이-

N의 범위와 각 단어의 길이가 작으므로 완전탐색을 이용하여 문제를 해결했다.

길이가 같은 모든 단어끼리 비교를 하며, 뒤집었을때 같은 단어인지 판별해준 뒤, 뒤집었을때 같은 문자열이 된다면 출력을 해준다. 다만 자기자신과도 비교를 해서 뒤집었을때 같은 단어라면 비밀번호이므로, 자기 자신도 고려해주어야 한다.

 

-시간복잡도-

모든 단어를 서로 비교해야하므로 O(N²)이 된다.

 

-코드-

#include <algorithm>
#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<string> v;

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string st;
        cin>>st;
        v.push_back(st);
    }
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(v[i].size()==v[j].size()){
                bool flag=true;
                int sz=v[i].size();
                for(int k=0;k<sz;k++){
                    if(v[i][k]!=v[j][sz-1-k]){
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    cout<<sz<<" " <<v[i][sz/2];
                }
            }
        }
    }
}