👩‍💻🔠 [baekjoon] 17609번: 회문

🖍️ solution

import sys

"""
[시간]
1) 14:20 ~ 14:45

[요약]
1) 유사회문: 한 문자를 삭제하여 회문으로 만들 수 있는 문자열
    => 유사회문인지 아닌지 판단하는 프로그램 작성
2) 주어진 문자열의 길이는 10만, 문자열 개수는 최대 30개
    => 제한 시간이 1초라서 O(n)의 알고리즘을 설계 필요, Counter 사용 불가
[전략]
1) 슬라이싱 이용해서 원본과 뒤집은 문자열을 비교하는 과정에서 걸러내기 (루프 하나만 쓰게 만들 수 있음)
    - 각 자리를 대조하면 가장 처음 다른 문자가 등장하는 지점을 찾아재 해당 문자를 제거함.
    - 제거하는 것도 두가지 케이스가 발생, 둘 중 하나만 만족해도 유사 팰린드롬으로 판정
        => 원본의 문자 제거
        => 역본의 문자 제거
"""
for _ in range(int(sys.stdin.readline())):
    checker1, checker2 = '', ''
    text = sys.stdin.readline().rstrip()
    tmp_pal = text[::-1]

    # pure palindrome
    if text == tmp_pal:
        print(0)
        continue

    # similar palindrome or not
    for i in range(len(text)):
        if text[i] != tmp_pal[i]: 
            checker1 = checker1 + text[i+1:] # remove original text's char
            checker2 = checker2 + tmp_pal[i+1:] # remove reversed text's char
            break
        checker1 += text[i]
        checker2 += tmp_pal[i]

    if checker1 == checker1[::-1] or checker2 == checker2[::-1]:
        print(1)
    else:
        print(2)

💡 idea

• 1) 슬라이싱을 이용한 풀이
  • 원본과 슬라이싱으로 뒤집은 문자열을 철자 하나 하나 비교 (문자열 길이 및 시간 제한 때문에 이중 루프는 불가)
    • linear search 하면서, 처음으로 다른 철자가 등장하는 지점을 찾아 해당 문자를 제거, 제거는 두가지 케이스 발생
      • 원본의 철자를 제거하는 경우
      • 역본의 철자를 제거하는 경우
  • 두가지 케이스 중에서 하나라도 만족한다면 유사 팰린드롬으로 판정

시간압박이 있는 상황에서 슬라이딩 윈도우과 포인터 혼합 방식을 깔끔하게 구현하는 것이 생각보다 쉽지 않아서, 직관적으로 코드를 빠르게 만들 수 있는 슬라이싱 대조 방식을 선택하게 되었다. 혼합 방식에 비해 덜 엘레강스하고 느리지만, 훨씬 직관적인 풀이라고 생각한다.

철자 제거할 때 주의할 점은 원본과 역본 케이스 모두 고려해야 한다는 점이다. 둘 중 하나만 고려하면 반례에 걸리는게 생긴다. 필자는 처음에 무지성으로 역본의고 철자만 제거하는 방식으로 코드를 서술했다가 예제 입력 3번째 문자열에 의해 원본 역시 고려해야 함을 깨닫고 수정하게 되었다.