[백준 30089] 새로운 문자열 만들기

문제 출처 : https://www.acmicpc.net/problem/30089

30089번: 새로운 문자열 만들기

이 문제는 제 1회 청소년 IT 경시대회 초등부 A번, 중등부 A번으로 출제되었습니다.

문자열 S가 주어졌을 때 뒤집어도 문자열 S가 나오는 가장 짧은 문자열 X를 출력하는 문제 입니다.

테스트 케이스가 100개 이하이고, 문자열 길이가 20 이하이기 때문에 시간 복잡도에 구애받지 않고 어렵게 생각하지 않고 풀어도 됩니다.

문제 이해하기

이렇게 앞으로 읽어도, 거꾸로 읽어도 똑같은 문자열을 팰린드롬(palindrome) 또는 회문이라고 합니다. 보통 회문인지 아닌지 판별하는 문제가 많은데 여기서는 주어진 문자열을 가지고 회문을 만들어야 합니다. 회문을 만드는 방법은 여러가지가 있는데 그 중 가장 짧은 회문을 만들어야 하는 것이 중요합니다. 보통 가장 쉽게 회문을 만드는 방법은 다음과 같습니다.

“BANADA”라는 단어가 있으면 이를 뒤집어 연결합니다. 그럼 BANADAADANAB 가 되어 회문이 됩니다. 하지만 이 문제에서는 가장 짧은 회문을 만들어야 하는 것이 핵심입니다. 이를 위해 회문인 부분과 회문이 아닌 부분으로 나누어주어야 합니다.

BANADA를 두 부분으로 나누면 회문이 아닌 BAN과 회문인 ADA로 나눌 수 있습니다. 회문인 ADA를 그대로 놔두고 회문이 아닌 BAN만 뒤집어 뒤로 붙이면 됩니다.

 

이렇게 하면 BANADANAB 라는 회문을 만들 수 있습니다.

문제 해결하기

그럼 아래와 같은 규칙을 만들 수 있습니다.

1. 문자열을 회문이 아닌 부분과 회문인 부분으로 나누기
2. 회문이 아닌 부분을 뒤집어 문자열에 붙이기

이렇게 두 부분으로 나누어 문제를 해결하면 됩니다.

파이썬에서 사용하는 슬라이싱에 대한 이해가 충분히 있어야 아래 코드를 보는데 무리가 없습니다. 아직 슬라이싱에 대해 잘 모른다면 아래 링크를 확인 부탁 드립니다.

https://wikidocs.net/192334#1-

01. 리스트 기본 사용방법

코드 작성하기

그럼 코드를 작성하며 문제를 해결해 보겠습니다.

입력받기

T = int(input())

for _ in range(T):
    S = input()
    print(solve(S))

테스트 케이스 갯수 T를 입력 받습니다. 다음으로 T개의 문자열 S를 입력받아 solve라는 함수를 사용하여 문제를 해결해 X를 찾아 출력해 줍니다.

solve 함수

def solve(S):  
    for i in range(len(S)):
        if S[i:] == S[i:][::-1]:
            if i == 0:
                break
            S += S[i - 1::-1]
            break
    return S

문자열 S에서 한 글자씩 이동하며 뒤집어 비교를 합니다. 위에서 예를 들었던 BANADA를 예를 들면 i가 0일 때에는 S[i:] 은 BANADA가 됩니다. 이 값을 뒤집으면 ADANAB가 되어 틀립니다. i값이 3이 되었을 때 S[3:]은 ADA가 됩니다. 이것을 뒤집은 S[3:][::-1] 역시 ADA가 됩니다. 배열 S의 3번째 인덱스부터 마지막 인덱스까지를 나타내는 것이 S[3:]가 되고, 이것을 뒤집기 위해 [::-1] 을 붙여준 것 입니다.

i가 0이 아니기 때문에 원래 S값에 S[2::-1]인 NAB를 뒤에 연결해 줍니다. 결국 답은 BANADANAB가 됩니다.

만약 i값이 0인 경우는 그냥 종료시켜주어야 합니다. ROTATOR의 경우 처음부터 회문입니다. S값에 뒤집은 S값을 더해주면 ROTATORROTATOR이 되기 때문 입니다.

전체 코드

전체 코드를 확인해 보겠습니다.

T = int(input())

def solve(S):  
    for i in range(len(S)):
        if S[i:] == S[i:][::-1]:
            if i == 0:
                break
            S += S[i - 1::-1]
            break
    return S

for _ in range(T):
    S = input()
    print(solve(S))