[BOJ-10174] 팰린드롬 (Python)

🤒 문제

BOJ-10174 팰린드롬

💊 풀이1 (pop)

팰린드롬 : 팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 단어나 숫자들을 말한다.

따라서 앞뒤, 앞뒤, 앞뒤가 같은지 차례대로 검사하면 된다.
앞에서 pop(0)한것과 뒤에서 pop()한것이 같은지 검사하면 된다.
핵심은, 문자열이 홀수개로 이루어져 있을 때 while(case)와 같은 방법을 사용한다면 빈 리스트에서 pop하게 되므로 len(case) > 1까지 검사한다. 한 개만 남았을 경우엔 앞 뒤가 다 같아서 통과된 것이므로 팰린드롬이 맞다.

deque 사용한 이유

pop(0) 은 시간복잡도가 O(n),
deque의 popleft()는 시간복잡도가 O(1)이기 때문이다.
실제로, 제출 해보면 deque를 사용한 풀이가 더 빠르다.
테스트 케이스가 더 많아질 경우 이것보다 차이가 더 클 것이므로 웬만하면 deque를 쓰자!

• pop(0)

def is_palindrome(case):
    while(len(case) > 1):
        if case.pop(0) is not case.pop():
            return False
        else:
            continue
    return True

• deque 의 popleft()

def is_palindrome(case: Deque):
    while(len(case) > 1):
        if case.popleft() is not case.pop():
            return False
        else:
            continue
    return True

아래는 완성된 전체 소스코드이다.

💊 풀이2 (투포인터)

말 그대로, 포인터 2개로 푼 풀이이다.
1. 처음에 front 포인터는 0번째 인덱스를 가리키고, back 포인터는 맨 뒤를 가리킨다.
2. while문을 back이 front보다 클 동안 도는데, 이때 case[front] 와 case[back] 이 일치하지 않으면 팰린드롬이 아니므로 바로 False를 리턴한다.
3. 일치 할 경우엔 front를 1 증가시키고, back를 1 감소시킨다.

이런 느낌이다.

✨ 소스코드

1

from collections import deque
import collections
from typing import Deque
import sys

def is_palindrome(case: Deque):
    while(len(case) > 1):
        if case.popleft() is not case.pop():
            return False
        else:
            continue
    return True

N = int(input())
for _ in range(N):
    case = collections.deque(sys.stdin.readline().strip().lower())
    if is_palindrome(case):
        print("Yes")
    else:
        print("No")

2

import sys

def is_palindrome(case: list):
    front = 0
    back = len(case) - 1

    while(front < back):
        if case[front] is not case[back]:
            return False
        front += 1
        back -= 1
    return True


N = int(input())
for _ in range(N):
    case = sys.stdin.readline().strip().lower()
    if is_palindrome(case):
        print("Yes")
    else:
        print("No")