Pr.10988 팰린드롬인지 확인하기

Pr.10988 팰린드롬인지 확인하기

문제

알파벳 소문자로만 이루어진 단어가 주어진다. 이때, 이 단어가 팰린드롬인지 아닌지 확인하는 프로그램을 작성하시오. 팰린드롬이란 앞으로 읽을 때와 거꾸로 읽을 때 똑같은 단어를 말한다. level, noon은 팰린드롬이고, baekjoon, online, judge는 팰린드롬이 아니다.

입력

첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 팰린드롬이면 1, 아니면 0을 출력한다.

예제 입력

#1.
level

#2.
baekjoon

예제 출력

#1. 
1

#2.
0

풀이과정

전제조건

1. 시간 복잡도, 공간 복잡도
   • for문을 사용하여 시간 복잡도는 o(n)이다.
2. 최대, 최소 조건
   • 최소 탐색 횟수는 1, 최대 탐색횟수는 50
3. 사용 알고리즘
   • 단순 구현 문제

     1. 단어를 입력받는다.
     2. 뒤짚은 문자열 s2를 만든다.
        • std::reverse를 사용하여 문자열을 뒤집는다.
     3. for문을 사용하여 문자열의 절반 까지만 비교를 한다.

4. 반례
   • 홀수의 경우

제출 코드

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

string s1, s2;

int main(){
    cin >> s1;
    s2 = s1;
    reverse(s1.begin(), s1.end());
    for (int i = 0; i < s1.size() / 2; i++){
        if (s1[i] != s2[i]){
            cout << 0;
            return 0;
        }
    }
    cout << 1;
    return 0;
}

해설

생각해볼 점

• 문자열을 뒤짚는 방안 : std::reverse를 사용하여 문자열을 뒤집는다.

  • string의 복사 : deep copy를 사용하여 문자열을 복사한다.</br>
  • string은 char형 배열과 다르게 깊은 복사를 사용하여 s2에 s1을 할당하면 새로운 메모리 공간에 복사된다.

• string 비교 : string은 == 연산자를 사용하여 비교할 수 있다.

  • s1 == s2와 같은 문자열 비교는 내부적으로 두 문자열의 모든 문자를 처음부터 끝까지 순차적으로 비교한다.
  • C++의 std::string에서 == 연산자는 다음과 같은 과정으로 비교한다.
    1. 먼저 문자열 길이를 비교합니다 (길이가 다르면 바로 false 반환)
    2. 길이가 같다면 각 위치의 문자를 처음부터 끝까지 하나씩 비교합니다
    3. 모든 문자가 같으면 true, 하나라도 다르면 false를 반환합니다

수정방안

• if(temp == s) cout << 1; 비교로 한번에 처리 가능하다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
string s,temp;
int main(){
    cin >> s;
    temp = s;
    reverse(temp.begin(),temp.end());

    if(temp == s) cout << 1;
    else cout << 0;
    return 0;
}