백준 25501번 풀이

문제

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

25501번: 재귀의 귀재

회문 판독을 재귀함수로 한다. 문제 제목도 회문. 

 

Reference

https://my-coding-notes.tistory.com/580

[🥉2 / 백준 25501 / 파이썬] 재귀의 귀재

 

풀이

일단 회문은 거꾸로 해도 같은 게 회문이다. 스위스 기러기 토마토 이런것도 회문이고, 여보 안경 안보여도 회문. 띄어쓰기 빼고 보면 회문 맞다. 근데... 이거... 거꾸로 뒤집은거랑 같으면 회문 콜 하면 되는거 아니었냐... 왜 재귀맛이...

 

참고로 제한효소 시퀀스도 회문이다. 예? 왜죠? 

5'-GAATTC-3'
3'-CTTAAG-5'

각각 5'에서 3' 방향으로 읽어보자.

 

참고로 이번 문제는 떠먹여주는 힌트가 있는데, 그걸 고대로 내면 안 되고 두 가지 요소를 추가해야 한다. 첫번째가 몇 번 호출했나이고 두번째가 입력 반복문으로 받는거다.

 

def recursion(s, l, r):
    if l >= r: return 1
    elif s[l] != s[r]: return 0
    else: return recursion(s, l+1, r-1)

def isPalindrome(s):
    return recursion(s, 0, len(s)-1)

print('ABBA:', isPalindrome('ABBA'))
print('ABC:', isPalindrome('ABC'))

이게 그 떠먹여주는 코드. 

 

일단 저 두 함수가 뭐 하는거냐... 아래 함수는 입력받아서 인자로 넘겨주는 함수고 위 함수는 인자로 넘겨받은 문자가 회문인지 판독해준다. 근데 문자열 하나 받는데 인자가 3개가 넘어간다? 맨 오른쪽건 문자열 길이-1이다. 어? 인덱싱??? 그렇다.

 

예시에 나온 ABBA를 예로 들어보면 ABBA, 0, 3이 넘어가게 되는데

1) ABBA, 0, 3 -> 0번째랑 3번재가 같네? -> 0 < 3이므로 크거나 같지 않음 -> ABBA, 1, 2
2) ABBA, 1, 2 -> 1번째랑 2번째가 같네? -> 1 < 2이므로 크거나 같지 않음 -> ABBA, 2, 1
3) ABBA, 2, 1 -> 2 > 1이므로 리턴 1

이렇게 된다. (홀수일때는 0,4->1,3->2로 같아지기때문에 끝)

 

for i in range(T):
    S = sys.stdin.readline().strip()
    print(isPalindrome(S))

입력 여러개 받는 건 그냥 이렇게만 해도 된다. 단, sys.stdin.readline()으로 받을때는 공백을 반드시 떼주자. 

 

import sys 
T = int(sys.stdin.readline())

def recursion(s, l, r):
    global count
    count += 1

    if l >= r: 
        return 1
    elif s[l] != s[r]: 
        return 0
    else: 
        return recursion(s, l+1, r-1)

def isPalindrome(s):
    return recursion(s, 0, len(s)-1)

for i in range(T):
    count = 0
    S = sys.stdin.readline().strip()
    print(isPalindrome(S), count)

횟수 세 주는건 유서깊은 count인데... 이제 문제가 있다. 저걸 함수 안에서 선언하고 더하면 괴랄하게 된다. 그리고 for문에서 선언해버리면 함수 입장에서 count는 없는 변수가 돼서 미쳤습니까 휴먼? 한다. 그래서 global로 전역 번수 선언을 해 줘야 한다.