17609번 회문

개발새발log·2023년 3월 20일
0

백준

목록 보기
16/36

맞왜틀 기록하기 ~

문제

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

접근 방식

투포인터를 활용해서 풀 수 있다.

처음부터 회문 통과면 0,

그게 아니라면 하나씩 좁혀가며 왼쪽 끝을 제거한 결과와, 오른쪽 끝을 제거한 결과끼리 비교할 수 있다.

둘 다 안 되는 경우 2를 반환하면 된다.

초기 코드 (실패)

def solution():
    S = input()

    # 투포인터
    res = 0  # 삭제 없이 완전한 회문인가?
    s, e = 0, len(S) - 1
    while s < e:
        if S[s] == S[e]:
            s += 1
            e -= 1
        else:
            if res == 1:  # 이미 한번 삭제 거친 경우
                res = 2
                break
                
            res = 1
            # 왼쪽 삭제 츄라이 ~
            if s + 1 < e and S[s + 1] == S[e]:
                s += 2
                e -= 1
            # 오른쪽 삭제 츄라이 ~
            elif e - 1 > s and S[s] == S[e - 1]:
                s += 1
                e -= 2
            else:
                res = 2
                break

    return res

# 입력부
t = int(input())
for _ in range(t):
    print(solution())

끝에서부터 줄여가며 끝과 끝 글자를 비교하며 업데이트 하는 방식이다.

한동안 여기서 크게 벗어나지 못한채 맞왜틀을 부르짖고 있었다.
그러다 발견한 빛과 소금같은 반례 .. 🥹✨

- "aapqbcbqpqaa"

"pqbcbqpq" -> 여기서 복병인 게, 이 코드에 의하면 "pqbcbqp"도, "qbcbqpq"도 일단 통과하기 때문이다. (조건문 순서에 의해 "qbcbqpq"가 통과해버린 것 -> 2가 나온 것)

그제서야 한쪽 끝을 짤랐을 때, 회문인지 판별하고 끝내야하는구나 깨달았다.

수정된 코드 (성공)

def solution():
    S = input()

    # 완전한 회문인가?
    if S == S[::-1]:
        return 0

    # 1인가 2인가 -> 투포인터
    s, e = 0, len(S) - 1
    while s < e:
        # 불일치 하는 자리 찾을 때까지 좁혀 가기
        if S[s] == S[e]:
            s += 1
            e -= 1
        else:
            # 양쪽 끝 삭제 츄라이 ~ !
            ltmp, rtmp = S[s + 1: e + 1], S[s: e]
            if ltmp == ltmp[::-1] or rtmp == rtmp[::-1]:
                return 1
            else:
                return 2
profile
⚠️ 주인장의 머릿속을 닮아 두서 없음 주의 ⚠️

0개의 댓글