Palindrome · 알고리즘 노트

개념

양 끝에서 비교하기

팰린드롬은 앞에서 읽은 문자열과 뒤에서 읽은 문자열이 같은 문자열입니다. LEVEL과 ABBA는 팰린드롬입니다.

맨 앞과 맨 뒤 문자를 비교하고 두 위치를 안쪽으로 한 칸씩 이동합니다. 서로 다른 문자를 만나면 팰린드롬이 아닙니다. 두 위치가 만나거나 교차할 때까지 모두 같으면 팰린드롬입니다. 홀수 길이 문자열의 가운데 문자는 비교할 짝이 필요하지 않습니다.

LEVEL에서는 첫째·다섯째 문자인 L끼리, 둘째·넷째 문자인 E끼리 비교합니다. 두 쌍이 같고 가운데 V는 뒤집어도 자기 위치이므로 팰린드롬입니다. LEVER에서는 첫 쌍 L, R이 다르므로 바로 판정을 끝낼 수 있습니다.

문자열을 뒤집으면 위치 $i$ 의 문자가 반대편 위치로 이동합니다. 따라서 모든 대칭 위치의 문자가 같은지 확인하는 것으로 문자열 전체가 같은지를 판별할 수 있습니다. 한 문자열 전체의 회문 여부를 검사할 때 이 방법을 사용합니다.

복잡도

문자열 길이를 $N$ 이라고 합니다.

연산	시간복잡도	공간복잡도
양 끝 비교	$O(N)$	추가 $O(1)$

예제

문제

주어진 문자열이 팰린드롬인지 판별하여라.

입력

첫째 줄에 영어 대문자로 이루어진 문자열 $S$ 가 주어진다. 길이는 $1$ 이상 $100$ 이하이다.

출력

팰린드롬이면 YES, 아니면 NO를 출력한다.

예제 코드

C++20

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    int l, r;
    bool ok;

    cin >> s;
    l = 0;
    r = (int)s.size() - 1;
    ok = true;

    while (l < r) {
        if (s[l] != s[r]) {
            ok = false;
            break;
        }
        ++l;
        --r;
    }

    cout << (ok ? "YES" : "NO") << '\n';
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc;
        String s;
        int l, r;
        boolean ok;

        sc = new Scanner(System.in);
        s = sc.next();
        l = 0;
        r = s.length() - 1;
        ok = true;

        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                ok = false;
                break;
            }
            ++l;
            --r;
        }

        System.out.println(ok ? "YES" : "NO");
    }
}

Python 3

s = input()
l = 0
r = len(s) - 1
ok = True

while l < r:
    if s[l] != s[r]:
        ok = False
        break
    l += 1
    r -= 1

print("YES" if ok else "NO")

2.19.1 Palindrome

개념

양 끝에서 비교하기

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드