[백준/c++] 17609 회문

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

17609번: 회문

 

✨ 문제 풀이

문장의 앞에서 부터 문자를 짚어나가는 포인터와, 맨 뒤에서부터 문자를 짚어나가는 포인터 두 개를 이용하는 문제입니다.

앞에서부터 보는 포인터를 x, 뒤에서부터 보는 포인터를 y라고 정의합니다.

문장의 길이가 홀수일 때 가운데 문자는 무엇이든 상관없고 짝수일 때는 x=y-1일 때까지 비교하므로 x<y의 조건을 만족할 때 while문을 사용합니다.

 

저는 현재 문장이 회문인지 확인할 수 있는 isPalindrome() 함수를 만들었습니다. isPalindrome() 에서는 x, y 포인터를 한 칸씩 옮겨가며 서로 다른 문자를 가지게 되면 false를 반환하고, 계속 같은 문자를 갖게 되면 true를 반환합니다.

 

그리고 회문인지, 유사회문인지, 무엇도 아닌지를 확인하고 주어진 정수(0, 1, 2)를 반환하는 함수 getPalindromeScore() 를 만들었습니다.

• 함수를 실행하자마자 문장을 검사했는데 회문임 - 0 반환
• 회문이 아니라면 x와 y가 어디서 서로 다른 문자를 가리키는지 찾음
  • x가 가리키는 문자를 삭제한 문장이 회문이거나 y가 가리키는 문자를 삭제한 문장이 회문임 - 1 반환
  • 둘 다 회문이 아님 - 2 반환
• 위 과정을 모든 문자에 대해서 x<y일 때까지 반복했으나 회문이 아님 - 2 반환

이렇게 문제를 해결할 수 있었습니다.

 

🗓 코드

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

bool isPalindrome(string sentence) {
    int x=0, y=sentence.size()-1;
    while (x<y) {
        if (sentence[x]!=sentence[y]) return false;
        x++; y--;
    }
    return true;
}

int getPalindromeScore(string sentence) {
    if (isPalindrome(sentence)) return 0;

    int x=0, y=sentence.size()-1;
    while (x<y) {
        if (sentence[x]!=sentence[y]) {
            string newSentenceWithoutX = sentence.substr(0, x) + sentence.substr(x+1);
            string newSentenceWithoutY = sentence.substr(0, y) + sentence.substr(y+1);
            if (isPalindrome(newSentenceWithoutX) || isPalindrome(newSentenceWithoutY))
                return 1;
            else return 2;
        }
        x++; y--;
    }
    return 2;
}

int main(void) {
    int T;
    cin >> T;
    vector<string> sentences;
    for (int i=0;i<T;i++) {
        string input;
        cin >> input;
        sentences.push_back(input);
    }
    
    for (string s : sentences) {
        cout << getPalindromeScore(s) << '\n';
    }
    return 0;
}