[구현/문자열] 백준 17609 회문 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

17609번: 회문

 

 

 

2. 문제 풀이

 주어진 문장이 회문, 유사회문 또는 회문이 아닌지 판별하는 문제입니다.

 

2022.03.02 - [Algorithm] - [구현/문자열] 백준 1254 팰린드롭 만들기 - 파이썬(Python)

[구현/문자열] 백준 1254 팰린드롭 만들기 - 파이썬(Python)

 위 문제와 비슷합니다. 맨 첫 문자와 맨 끝 문자가 같은지 비교하고, 같으면 한 문자씩 안쪽으로 이동합니다. 만약 다르면, 앞 문자 또는 뒷 문자를 제거하고 회문을 검사합니다. 제거한 뒤 회문이 맞다면 유사회문입니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    s = input().rstrip()
    #회문
    if s == s[::-1]:
        print(0)
        continue
    #유사회문
    for i in range(len(s)):
        subS = s[0:i] + s[i+1:]
        if subS == subS[::-1]:
            print(1)
            break
    #회문아님
    else:
        print(2)

  맨 처음에는 슬라이싱으로 '날먹' 쉽게 구현하려 했습니다. 시간제한이 1초(추가 시간 없음)인게 싸늘하더니... 시간초과가 났습니다.

 

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    s = input().rstrip()
    left = False
    right = False
    # 한 칸씩 당기며 앞과 뒤를 비교
    for i in range(len(s) // 2):
        #앞뒤 문자가 맞지 않음
        if s[i] != s[len(s) - 1 - i]:
            #맨 가운데 비교인데 아직 틀린 게 없으면 유사회문
            if len(s) - 1 - i*2 == 1 and not left and not right:
                print(1)
                break
            # 앞 글자 삭제 후 계속해서 비교
            for j in range(i, len(s)//2):
                # 그 후로도 또 맞지 않는 문자가 있으면 앞쪽 제거로는 유사회문 못 만듬
                if s[j + 1] != s[len(s) - 1 - j]:
                    left = True

            # 뒤 글자 삭제 후 계속해서 비교
            for j in range(i, len(s)//2):
                # 그 후로도 또 맞지 않는 문자가 있으면 뒤쪽 제거로는 유사회문 못 만듬
                if s[j] != s[len(s) - 1 - j - 1]:
                    right = True

            # 앞과 뒤가 둘 다 안맞으면 회문이 아님
            if left and right:
                print(2)
                break
            # 앞 또는 뒤 중 1쪽을 빼면 회문이 됨 = 유사회문
            elif left or right:
                print(1)
                break
    #앞뒤가 다 맞았으면 회문
    else:
        print(0)

 두 번째 방법은 left와 right 포인터로 하나하나 비교합니다. 퀵 정렬 알고리즘을 알고 계시면 투 포인터로 비교하는 로직이 익숙하실 듯 합니다.

 유의할 테스트 케이스는 'abca'와 같은 경우입니다. b와 c 중 아무거나 제거해도 유사회문이 됩니다. 이 경우는 따로 조건문으로 판별해줍니다.