BOJ 1259. 팰린드롬 수 (Python)

BOJ 1259. 팰린드롬 수

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

1259번: 팰린드롬수

Logic

팰린드롬이란 앞 뒤가 같은 것이다. 토마토, 기러기 같은.

앞에서부터 뽑고, 뒤에서부터 뽑은것이 끝까지 일치한다면 이것은 팰린드롬 수 일것이다.

 

 

한번이라도 일치하지 않는다면 그것은 팰린드롬 수가 아니다.

 

0이 나올때까지 While문을 돌며 input한것을 deque에 저장한다.

 

이때 그냥 list를 사용하지 않고 덱을 쓰는 이유는, 파이썬의 리스트에서 .pop(0)을하면 시간복잡도가 O(n)이 되기 때문이다. 따라서 앞, 뒤에서 pop할수있는 deque를 사용하면 실행 시간을 줄일 수 있다.

case = sys.stdin.readline().strip()

if case == "0":
    break

deq = collections.deque(list(map(int,case)))

 

덱에 input한것을 담고 나서 다시 while문을 돈다.

len(deq)이 1이 될 때까지 break하지 않으면 이것은 길이가 홀수인 팰린드롬수이니 "yes"를 프린트하고 while문을 종료한다.

if len(deq) == 1:
    print("yes")
    break

 

한번이라도 일치하지 않으면 "no"를 출력하고, len(deq)이 0이면서 left와 right가 일치하면 이것은 길이가 짝수인 팰린드롬수이기 때문에 "yes"를 프린트하고 while문을 종료한다.

left = deq.popleft()
right = deq.pop()

if left != right:
    print("no")
    break

if left == right and len(deq) == 0:
    print("yes")
    break

 

Solution 1

import sys
import collections

while True:
    case = sys.stdin.readline().strip()

    if case == "0":
        break

    deq = collections.deque(list(map(int,case)))

    while True:
        if len(deq) == 1:
            print("yes")
            break

        left = deq.popleft()
        right = deq.pop()

        if left != right:
            print("no")
            break

        if left == right and len(deq) == 0:
            print("yes")
            break

여기서부턴 좀 편법인데,,,

Solution 2

import sys

while True:
    case = sys.stdin.readline().strip()

    if case == "0":
        break
    
    case = list(case)

    if case == list(reversed(case)):
        print("yes")
    else:
        print("no")

파이썬 내장함수인 reverse()나 reversed()를 사용해서 풀 수 있다.

 

Solution 3

import sys

while True:
    case = sys.stdin.readline().strip()

    if case == "0":
        break

    if case == case[::-1]:
        print("yes")
    else:
        print("no")

Python의 슬라이싱을 이용해서 풀 수도 있다.

 

 

하지만 이게 코딩테스트나 면접에서 나온다고 하면 2,3처럼 풀면 안될거같다 .. ㅎㅎ 고로 1처럼 푸는 방법을 알아야 할 것이다.