회문(팰린드롬)

팰린드롬

회문(Palindrome)이란 앞에서부터 읽거나 뒤에서부터 읽을 때 같은 문자열이 나오는 문자열을 회문(팰린드롬)이라고 말합니다.

예시

  • abcba: 제대로 읽으면 abcba, 거꾸로 읽으면 abcba이므로 회문입니다.

  • pqpq: 제대로 읽으면 pqpq, 거꾸로 읽으면 qpqp이므로 회문이 아닙니다.

  • a1b2c3: 제대로 읽으면 a1b2c3, 거꾸로 읽으면 3c2b1a이므로 회문이 아닙니다.

  • 9999: 제대로 읽으면 9999, 거꾸로 읽으면 9999이므로 회문입니다.

  • z: 제대로 읽으면 z, 거꾸로 읽으면 z이므로 회문입니다.

팰린드롬 문제들은 크게 두가지로 나눌 수 있습니다.

  1. 문자열 전체가 하나의 팰린드롬인가?

  2. 이 문자열의 부분 문자열이 팰린드롬인가?

우리가 이번에 배울 항목은 1번에 관한 내용이며, 2번에 관한 내용은 Manacher's Algorithm이라는 고급 알고리즘 지식이 필요하여 여기에서 다루지 않습니다.

팰린드롬인지 판별하기

위에 있는 예시를 살펴보면 팰림드롬 문자열이 가지고 있는 특징을 찾을 수 있는데요.

바로 팰림드롬 문자열은 문자열이 좌우 대칭이라는 것입니다.

s = '1010101'

만약 위와 같은 문자열이 있다고 가정해보면, s[0] = s[6], s[1] = s[5], s[2] = s[4]인 것이죠.

그래서 팰린드롬 여부는 for문이나 while문을 이용하여 len(s)//2번 반복하여 팰린드롬인지 파악할 수 있습니다.

for문으로 구현하기

팰린드롬 여부를 따져보는 코드를 만들기 전에 먼저 문자열을 입력 받는 s와 flag = True라는 bool변수를 만들어줍시다.

s = input()
flag = True

flag 변수는 팰린드롬이면 True이고, 팰린드롬이 아니라면 False로 변경되는 변수입니다.

이제 for문을 이용하여 팰린드롬인지 확인해야 하는데요. 우리는 앞에서부터 시작하는 문자와 뒤에서부터 시작하는 문자를 서로 비교하므로 한 번의 반복문에 총 2개의 문자를 확인할 수 있습니다. 그래서 for문은 len(s)//2번 반복해주시면 됩니다.

s = input()
flag = True
for i in range(len(s)//2):
    blah blah

이제 서로 문자를 비교해야 하는데, 앞에서부터 읽는 방법은 단순히 s[i]를 해주면 됩니다. 뒤에서부터 읽는 방법은 문자열의 마지막 인덱스부터 시작해야하므로 문자열의 마지막 인덱스는 len(s)-1이니 s[len(s)-1-i]를 이용하여 뒤에서부터 읽을 수 있습니다.

그리고 이때 s[i]와 s[len(s)-1-i]의 값이 다르다면 팰린드롬이 아니므로 flag = False로 설정해야 합니다. 아니면 문자열의 마지막 인덱스는 s[-1]로도 표현할 수 있으므로 s[len(s)-1-i]대신 s[-1-i]로 표현할 수도 있습니다.

s = input()
flag = True

for i in range(len(s)//2):
    if s[i] != s[len(s)-1-i]:
        flag = False

print(flag)
s = input()
flag = True

for i in range(len(s)//2):
    if s[i] != s[-i-1)]:
        flag = False

print(flag)

이렇게해서 팰린드롬 여부를 확인할 수 있습니다.

여러가지 입력 값을 넣어보면 True인지 False인지 알 수 있습니다. 맨 위에서 언급한 예시 값들을 한 번 넣어보겠습니다.

while문으로 구현하기

이번에는 while문을 이용하여 팰린드롬 여부를 확인해보겠습니다.

s = input()
flag = True

x, y = 0, len(s)-1

준비물은 문자열 s, 팰린드롬인지 출력할 flag, while문에서 사용할 변수인 x와 y입니다.

x는 앞에서부터 읽고, y는 뒤에서 읽기 때문에 각각 값을 0과 len(s)-1로 초기화하였습니다.

s = input()
flag = True

x, y = 0, len(s)-1
while 1:
    if x >= y: break

while문을 이용하여 문자열 길이의 반절만큼만 반복할 것이므로 x의 값이 y보다 같거나 크면 break문을 이용하여 while문을 빠져나오게 만듭니다.

이제 s[x]와 s[y]를 비교하여 값이 다르면 flag = False로 설정해주시면 됩니다. 그리고 비교가 끝나면 x에는 1을 더해주고, y에는 1을 빼주어 다음 문자열을 비교할 수 있도록 만들어줍니다.

s = input()
flag = True

x, y = 0, len(s)-1
while 1:
    if x >= y: break
    if s[x] != s[y]: flag = False
    x += 1
    y -= 1

print(flag)

이렇게 우리는 for문과 while문으로 팰린드롬을 판별하는 방법을 배웠는데요. 두가지 방법중에 편한 방법을 선택해 사용하시면 됩니다.

연습문제

BOJ 13235

입력한 단어가 팰린드롬이면 true, 아니면 false를 출력하는 문제입니다.

이 문제는 위에서 배운 for문이나 while문을 그대로 사용해주면 되는 문제입니다. 저는 그냥 바로 위에 있는 while문 코드를 가져오겠습니다.

s = input()
flag = True

x, y = 0, len(s)-1
while 1:
    if x >= y: break
    if s[x] != s[y]: flag = False
    x += 1
    y -= 1

print(flag)

여기서 주의할 점은 출력할 때 True, False가 아닌 true, false를 출력해야 한다는 점입니다.

이 부분은 if / else문을 추가하면 됩니다.

s = input()
flag = True

x, y = 0, len(s)-1
while 1:
    if x >= y: break
    if s[x] != s[y]: flag = False
    x += 1
    y -= 1

if flag == True: print('true')
else: print('false')

BOJ 11068

입력 받은 수가 B진법으로 변환했을 때 팰린드롬이면 1을 출력하고, 어떠한 경우에도 팰린드롬이 될 수 없으면 0을 출력하는 문제입니다.

문제를 읽어보니까 B의 최대값이 64로 64진법까지 확인할 수 있다고 나와있는데요. 문제에서 따로 64진법은 각 숫자들이 어떤 문자와 매칭되는지 알려주지 않았습니다.

그런데 64진법으로 변환한 수를 출력하지 않는 것이므로 굳이 64진수로 변환할 필요 없이 몫과 나머지만을 구해주고 팰린드롬을 판별해도 될 것 같습니다.

일단 입력 값을 받는 코드를 짜봅시다.

t = int(input())
for i in range(t):
    s = int(input())

이제 s를 2진법부터 64진법까지 진법 변환을 해야 합니다. 일단 for문을 2부터 64까지 반복하는 반복문을 만들 수 있겠네요.

그리고 우리는 진법 변환을 해서 팰린드롬이 될 수 있는 값이 하나라도 있으면 1을 출력하는 것이므로 flag = False를 만들어줍시다. 이 값은 나중에 팰린드롬을 발견하면 flag = True로 값이 변경됩니다.

t = int(input())
for i in range(t):
    s = int(input())
    flag = False
    
    for j in range(2, 65):
        blah blah

이제 진법 변환을 해야하니 나머지 값을 저장해줄 val이라는 리스트를 만들어주고 while문을 이용하여 진법 변환을 해줍시다. s값은 for문에서 계속 사용해야하므로 다른 변수에 값을 저장하여 진법 변환을 해주어야 합니다.

문제에서 B진법이 코드에서는 j진법이므로 변수에 j를 계속 나누어주어서 나머지를 val에 저장하면 되겠습니다.

t = int(input())
for i in range(t):
    s = int(input())
    flag = False
    
    for j in range(2, 65):
        val = []
        x = s
        while True:
            if x == 0: break
            val.append(x%j)
            x //= j
        blah blah

여기까지 만들었으면 진법 변환은 해결하였으니 이제 팰린드롬을 판별해주어야 합니다.

여기서도 True 값을 가지고 있는 bool변수를 하나 만들어서 두 값을 비교할 때 서로 다른 값이 나오면 False로 변경하게 만들어줍니다. 마지막까지 True로 남아있으면 이것은 팰린드롬이겠네요.

t = int(input())
for i in range(t):
    s = int(input())
    flag = False
    
    for j in range(2, 65):
        val = []
        x = s
        while True:
            if x == 0: break
            val.append(x%j)
            x //= j
        
        is_palindrome = True
        for k in range(len(val)//2):
            if val[k] != val[-1-k]:
                is_palindrome = False

여기까지 만들어졌으면 이제 is_palindrome을 이용하여 팰린드롬이 맞으면 flag = True로 값을 설정해줍니다.

t = int(input())
for i in range(t):
    s = int(input())
    flag = False
    
    for j in range(2, 65):
        val = []
        x = s
        while True:
            if x == 0: break
            val.append(x%j)
            x //= j
        
        is_palindrome = True
        for k in range(len(val)//2):
            if val[k] != val[-1-k]:
                is_palindrome = False
        if is_palindrome == True:
            flag = True

이제 출력을 해주면 되는데요.

출력은 flag 값이 True면 한 번이라도 팰린드롬 수가 존재했다는 것이므로 1을 출력하고, flag 값이 False라면 팰린드롬 수가 존재하지 않았다는 것이므로 0을 출력해주면 됩니다.

t = int(input())
for i in range(t):
    s = int(input())
    flag = False
    
    for j in range(2, 65):
        val = []
        x = s
        while True:
            if x == 0: break
            val.append(x%j)
            x //= j
        
        is_palindrome = True
        for k in range(len(val)//2):
            if val[k] != val[-1-k]:
                is_palindrome = False
        if is_palindrome == True:
            flag = True
    
    if flag == True: print(1)
    else: print(0)

이 문제는 코드가 길어서 어려워 보이지만, 단순히 진법 변환과 팰린드롬 판별을 코드에 넣어서 합친 것이기 때문에 어려운 문제는 아닙니다.

풀어볼 문제

Previous진법 변환Next스택(stack)

Last updated