[백준] 8892. 팰린드롬 <C++>

www.acmicpc.net/problem/8892

8892번: 팰린드롬

 

 

방법1)

 

브루트포스 방법을 이용해 하나하나 골라보고, 

 

이렇게 고른 두 문자열을 합쳤을 때 큐 스택을 이용해 회문인지 판단해주었다.

 

 

#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;
 
void push_q_s(string str1, string str2, queue<char>& q, stack<char>& s);
int Palindrome(queue<char> q, stack<char> s);
void Clear_q_s(queue<char>& q, stack<char>& s);
 
int main() {
    int t;
 
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
 
    cin >> t;
    while (t--) {
        int n, sw = 0;
        queue<char> q;
        stack<char> s;
        string str[101];
        //---------필요 변수 선언-----------
 
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> str[i];
        //---------입력----------
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;   // 자기자신을 고르지 않기 위함
 
                Clear_q_s(q, s);  // 큐 스택을 비워줌
                push_q_s(str[i], str[j], q, s);  //큐 스택에 고른 두 개의 문자열을 담아줌
                sw = Palindrome(q, s);  //고른 두 개의 문자열이 팰린드롬인지 확인함
                if (sw) {  // 팰린드롬이라면 출력해주고 반복문을 종료
                    cout << str[i] << str[j] << '\n';
                    break;
                }
            }
            if (sw) break;
        }
        if (!sw) cout << 0 << '\n';
    }
 
    return 0;
}
 
 
 
void push_q_s(string str1, string str2, queue<char>& q, stack<char>& s) {
    for (int k = 0; k < str1.size(); k++) {
        q.push(str1[k]);
        s.push(str1[k]);
    }
    for (int k = 0; k < str2.size(); k++) {
        q.push(str2[k]);
        s.push(str2[k]);
    }
}
 
int Palindrome(queue<char> q, stack<char> s) {
    while (q.size()) {
        if (q.front() != s.top()) return 0;
 
        q.pop();
        s.pop();
    }
    return 1;
}
 
void Clear_q_s(queue<char>& q, stack<char>& s) {
    while (q.size()) q.pop();
    while (s.size()) s.pop();
}

 

 

 

 

 

 

방법2)

 

문자열이라는 특징을 이용해 큐, 스택 없이 더 간단하게 풀 수 있다.

 

 

#include <iostream>
#include <string>
using namespace std;
 
int Palindrome(string , string);
 
int main() {
    int t;
 
    cin >> t;
    while (t--) {
        int n, f = 0;
        string str[101];
 
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> str[i];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;  
 
                f = Palindrome(str[i], str[j]); 
                if (f) {  
                    cout << str[i] << str[j] << '\n';
                    break;
                }
            }
            if (f) break;
        }
        if (!f) cout << 0 << '\n';
    }
 
    return 0;
}
 
int Palindrome(string s1, string s2) {
    string str = s1 + s2;
    int left = 0;
    int right = str.size() - 1;
 
    while (left < right) {
        if (str[left] != str[right]) return 0;
 
        left++;
        right--;
    }
    return 1;
}