[Python] 백준 온라인 저지 17609 회문

목차

문제

---

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

17609번: 회문

설계&풀이

---

처음엔 별다른 알고리즘을 생각하지 않고 그냥 for문 돌려서 풀려고 했다.

그런데 결과는 시간초과. 뭘까 뭘까.. 생각을 하다가, 투포인터가 생각나서 투포인터로 풀어봤는데, 정답이었다.

처음 코드는 다음과 같다.

'''
1. 일반적인 회문 판단 함수, 정답을 출력하는 함수 두개로 나뉘어서 작업해주자
'''
import sys

t = int(input())

# 0, 1, 2중 하나 출력해주는 함수
def palindrome(string):
    if isPalindrome(string):
        return print(0)
    else:
        for i in range(len(string)):
            tempList = list(string)
            del tempList[i]
            ''.join(tempList)
            if isPalindrome(tempList):
                return print(1)
        return print(2)
    
# 팰린드롬 여부를 판단하는 함수
def isPalindrome(string):
    str = list(string)
    reversedStr = list(string)
    reversedStr.reverse()
    
    if reversedStr == str:
        return True
    else:
        return False

for i in range(t):
    string = sys.stdin.readline()
    palindrome(string)

 Palindrome 함수엔 0, 1, 2중에 골라서 내보내주고, isPalindrome은 회문 여부를 판단해준다.

결과적으로 맞는 코드긴 하지만, 시간초과가 나서 안된다.
투포인터를 이용해서 짠 코드는 다음과 같다.

'''
1. 일반적인 회문 판단 함수, 정답을 출력하는 함수 두개로 나뉘어서 작업해주자
2. 처음엔 for문으로 완탐했는데, 시간초과가 나서 투포인터로 바꿈.
3. 왼쪽과 오른쪽 모두 회문 여부를 판단해보고, 둘중 하나라도 회문이라면 1로 노출, 아니면 2로 하는 방식으로 진행
'''
import sys

t = int(input())

# 0, 1, 2중 하나 출력해주는 함수
def palindrome(string, left, right):
    if isPalindrome(string, left, right):
        return print(0)
    else:
        while left < right:
            # 문자열의 left인덱스와 right 인덱스가 같다면 left는 늘리고 right 는 줄인다.
            if string[left] == string[right] :
                left += 1
                right -= 1
            # 만약 같지 않다면, 현재 left 인덱스보다 +1 한놈과, right인덱스보다 -1 한놈을 둘다 회문 여부 판단하는 함수로 보낸다.
            # 둘 중 하나라도 회문이 되면 1 출력하고 끝
            else:
                leftPal = isPalindrome(string, left + 1, right)
                rightPal = isPalindrome(string, left, right - 1)
                
                if leftPal or rightPal:
                    return print(1)
                else:
                    return print(2)
    
# 팰린드롬 여부를 판단하는 함수
def isPalindrome(string, left, right):
    str = list(string)
    while left < right:
        if str[left] == str[right]:
            left += 1
            right -= 1
        else:
            return False
    return True

for i in range(t):
    string = sys.stdin.readline().rstrip()
    left = 0
    right = len(string) - 1
    palindrome(string, left, right)

투포인터 자체가 복잡한 알고리즘은 아니라서.. 그냥 주석이랑 코드 천천히 읽어보시면 이해될듯?! 

 

코드 GIT 주소

---

https://github.com/kkkapuq/AlgorithmStudy/blob/main/Python/220719_BOJ_17609_%ED%9A%8C%EB%AC%B8/1.py

GitHub - kkkapuq/AlgorithmStudy: 알고리즘 문제풀이

 

코드

---

'''
1. 일반적인 회문 판단 함수, 정답을 출력하는 함수 두개로 나뉘어서 작업해주자
2. 처음엔 for문으로 완탐했는데, 시간초과가 나서 투포인터로 바꿈.
3. 왼쪽과 오른쪽 모두 회문 여부를 판단해보고, 둘중 하나라도 회문이라면 1로 노출, 아니면 2로 하는 방식으로 진행
'''
import sys

t = int(input())

# 0, 1, 2중 하나 출력해주는 함수
def palindrome(string, left, right):
    if isPalindrome(string, left, right):
        return print(0)
    else:
        while left < right:
            # 문자열의 left인덱스와 right 인덱스가 같다면 left는 늘리고 right 는 줄인다.
            if string[left] == string[right] :
                left += 1
                right -= 1
            # 만약 같지 않다면, 현재 left 인덱스보다 +1 한놈과, right인덱스보다 -1 한놈을 둘다 회문 여부 판단하는 함수로 보낸다.
            # 둘 중 하나라도 회문이 되면 1 출력하고 끝
            else:
                leftPal = isPalindrome(string, left + 1, right)
                rightPal = isPalindrome(string, left, right - 1)
                
                if leftPal or rightPal:
                    return print(1)
                else:
                    return print(2)
    
# 팰린드롬 여부를 판단하는 함수
def isPalindrome(string, left, right):
    str = list(string)
    while left < right:
        if str[left] == str[right]:
            left += 1
            right -= 1
        else:
            return False
    return True

for i in range(t):
    string = sys.stdin.readline().rstrip()
    left = 0
    right = len(string) - 1
    palindrome(string, left, right)

 

결과

---

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡