회문

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

예제 출력 1

0
1
1
2
2
0
1

문제 풀이

틀린 풀이

t=int(input())

for _ in range(t):
    lst=input()
    front=0
    rear=len(lst)-1
    cnt=0
    while front<=rear:
        if lst[front]==lst[rear]:
            front+=1
            rear-=1
        elif lst[front]!=lst[rear]:
            cnt+=1
            if lst[front+1]==lst[rear]:
                front+=1
            elif lst[front]==lst[rear-1]:
                rear-=1
            else:
                cnt+=1
                break
    if cnt>=2:
        print(2)
    else:
        print(cnt)

단순하게 투 포인터를 이용하여 하나씩 비교하면 된다고 생각해서 짠 코드이다. 하지만 abbab의 경우를 생각해보면 front, rear 포인터 중 어떤 하나를 먼저 이동할지에 따라 답이 1이 나올수도, 2가 나올수도 있기 때문에 다른 풀이법을 생각해봐야했다.

그래서 front나 rear 포인터를 한 칸씩 이동한 뒤 그 이후에 한 칸 씩 이동한 경우에도 모두 같은 쌍이 이루어진다면 유사회문이라고 판단할 수 있겠다고 생각했다. 나온 풀이는 아래와 같다.

시간초과 발생한 풀이

t=int(input())

def check(front,rear,lst):
    if lst[front]==lst[rear]:
        return True
    else:
        return False

for _ in range(t):
    lst=input()
    front=0
    rear=len(lst)-1
    cnt=0
    if len(lst)%2==0:
        mid=len(lst)//2
        if lst[:mid]==lst[mid:][::-1]:
            print(0)
            continue
        else:
            print(2)
            continue
    while front<=rear:
        if lst[front]==lst[rear]:
            front+=1
            rear-=1
        elif lst[front]!=lst[rear]:
            cnt+=1
            if lst[front]==lst[rear-1]:
                if check(front+1,rear-2,lst):
                    rear-=1
            elif lst[front+1]==lst[rear]:
                if check(front+2,rear,lst):
                    front+=1
            else:
                cnt+=1
                break
    if cnt>=2:
        print(2)
    else:
        print(cnt)

답은 맞췄으나 시간초과가 발생했던 풀이이다. 결국 다른 사람의 풀이를 참고하여 문제를 풀었다.

최종 코드

t=int(input())

def check(front,rear,lst):
    while front<rear:
        if lst[front]==lst[rear]:
            front+=1
            rear-=1
        else:
            return False
    return True

for _ in range(t):
    lst=input()
    front=0
    rear=len(lst)-1
    cnt=0
    if lst==lst[::-1]:
        print(0)
        continue
    else:
        while front<rear:
            if lst[front]==lst[rear]:
                front+=1
                rear-=1
            else:
                one=check(front+1,rear,lst)
                two=check(front,rear-1,lst)
                if one or two:
                    print(1)
                    break
                else:
                    print(2)
                    break

정답이 된 코드는 위와 같다. front 포인터가 이동한 경우, rear 포인터가 이동한 경우 두 가지를 모두 이용하여 한 가지 경우라도 팰린드롬 공식이 성립된다면 그 문자열은 유사회문으로 판단할 수 있는 것이다.

그 판단을 check라는 함수에서 모두 판단하고, check 함수로 들어오는 경우에는 이미 한 칸을 소모한 상태(첫 if/else 문을 통과하여 한 문자가 다른 상태)이기 때문에 한 번이라도 다른 문자가 발생한다면 그대로 False를 반환하여 2를 출력한다.

두 번 체크를 해야한다는 사고에 도달하기까지도 시간이 걸렸고, 코드를 짜는데에도 어려움을 겪었던 문제이다. 여러 문제를 풀어보면서 알고리즘을 푸는 방법의 감을 잡아봐야할 것 같다.