Palindrome String

Q: 문자열이 회문인지 어떻게 확인하나요?

첫 번째 문자를 마지막 문자와 비교하고, 두 번째 문자를 끝에서 두 번째 문자와 비교하는 식으로 가운데를 향해 진행합니다. 어느 한 쌍이라도 다르면 문자열은 회문이 아니며, 모든 쌍이 일치하면 회문입니다. 양쪽 끝에서 시작해 안쪽으로 이동하는 두 인덱스를 사용하면 한 번의 순회로 이를 수행할 수 있습니다.

Q: 추가 메모리 없이 회문인지 확인할 수 있나요?

맞습니다. 두 포인터 검사는 문자를 제자리에서 읽고 인덱스 두 개만 저장하므로 추가 공간을 O(1) 사용합니다. s 를 뒤집은 문자열과 비교하는 방법은 더 짧게 작성할 수 있지만, n 개의 문자로 이루어진 두 번째 문자열을 만듭니다.

Q: 회문 문자열을 확인하는 시간 복잡도는 얼마인가요?

길이가 n 인 문자열에서는 O(n) 입니다. 두 포인터 검사는 최대 n / 2 번 비교하고 첫 번째 불일치에서 멈추므로, 첫 문자와 마지막 문자가 다른 문자열은 한 번 비교한 후 판별됩니다.

Q: 단일 문자는 회문인가요?

네. 한 글자는 양방향으로 읽어도 같으므로 답은 true 입니다. 두 포인터 루프에서 left 와 right 는 모두 인덱스 0에서 시작하고, 루프는 실행되지 않으며, 함수는 true 를 반환합니다.

입문투 포인터 배열과 문자열

+10

문자열은 level처럼 왼쪽에서 오른쪽으로 읽을 때와 오른쪽에서 왼쪽으로 읽을 때 동일하면 회문입니다. 소문자 영어 문자로 이루어진 문자열 s를 입력받아 s가 회문이면 true를, 그렇지 않으면 false를 반환하는 함수를 작성하세요.

함수

isPalindrome(s: string) → boolean

sstring: 확인할 소문자 문자열
반환값boolean: s를 어느 방향으로 읽어도 똑같으면 참

제약 조건

1 ≤ s.length ≤ 5 × 10⁴
s에는 소문자 영어 알파벳(a부터 z까지)만 포함되어 있습니다.

예제

입력: s = "racecar"
출력: true
설명: 바깥쪽부터 안쪽으로 비교하세요: r과 r, a와 a, c와 c. 가운데 e는 짝이 없고 짝이 필요하지도 않으므로 답은 true입니다.

입력: s = "abba"
출력: true
설명: 길이가 짝수이면 모든 문자에 짝이 있습니다. 두 a는 서로 짝을 이루고 두 b도 서로 짝을 이루므로 답은 true입니다.

입력: s = "coddy"
출력: false
설명: 첫 번째 글자 c와 마지막 글자 y는 이미 다르므로 coddy는 회문이 아니며 답은 false입니다.

제출 시 숨은 테스트 +16개

후속 질문

예를 들어 Was it a car or a cat I saw와 같은 문장은 대소문자, 공백, 문장 부호를 무시하면 회문입니다. 이러한 문자를 건너뛰도록 두 포인터를 어떻게 바꾸면 될까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

회문은 뒤집어도 자기 자신과 같으므로, 직접 확인하는 방법은 문자열을 뒤집어 비교합니다. 더 나은 방법은 아무것도 만들지 않습니다. 첫 번째 문자는 마지막 문자와 일치해야 하고, 두 번째 문자는 끝에서 두 번째 문자와 일치해야 하며, 이런 식으로 가운데를 향해 계속됩니다. 두 개의 인덱스가 안쪽으로 이동하며 제자리에서 각 쌍을 검사하고, 처음으로 일치하지 않는 쌍을 발견하면 멈춥니다.

문자열과 그 역순을 비교합니다

핵심 아이디어

s를 양방향에서 똑같이 읽을 수 있다는 것은 s가 뒤집은 문자열과 같다는 뜻입니다. 그러니 문자열을 뒤집어 비교하세요. racecar를 뒤집으면 racecar이고, coddy를 뒤집으면 yddoc이므로 서로 다릅니다.

뒤집은 문자열을 만들고 비교하면 각각 모든 문자를 한 번씩 확인하므로 시간 복잡도는 O(n)입니다. 뒤집은 복사본에는 문자가 n개 더 들어가므로 추가 공간 복잡도는 O(n)입니다. n = 5 × 10^4일 때 비교한 뒤 버릴 문자열을 만들기 위해 문자 50,000개가 사용됩니다.

또한 매번 전체 작업을 수행합니다. coddy는 첫 글자와 마지막 글자만으로 판별할 수 있지만, 이 방법은 확인하기 전에 다섯 글자를 모두 뒤집습니다.

알고리즘

언어의 reverse 함수나 마지막 문자부터 첫 번째 문자까지 반복하는 루프를 사용해 s의 역순을 만드세요.
역순을 s와 비교하세요.
두 값이 같으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

def isPalindrome(s):
    return s == s[::-1]

양쪽 끝에서 시작하는 두 포인터

핵심 아이디어

뒤집으면 인덱스 i의 문자가 인덱스 n-1-i로 이동하므로, 모든 i에 대해 s[i]가 s[n-1-i]와 같을 때만 s는 자신의 역순과 정확히 같습니다. 각 쌍은 이 목록에 두 번 나타나므로 왼쪽 절반만 확인하면 됩니다. left를 인덱스 0에, right를 인덱스 n-1에 놓고 두 문자를 비교한 다음, 두 포인터를 모두 안쪽으로 한 칸씩 이동합니다.

포인터가 만나거나 서로 지나치면 멈춥니다. racecar에서는 인덱스 쌍 (0, 6), (1, 5), (2, 4)를 확인한 다음 인덱스 3에서 만납니다. 가운데 있는 e에는 짝이 필요하지 않습니다. abba에서는 (0, 3)과 (1, 2)를 확인한 다음 서로 지나칩니다. 처음으로 서로 다른 쌍이 나오면 답이 false임이 증명되므로 즉시 반환합니다. 따라서 coddy는 비교 한 번으로 판별됩니다.

비교는 최대 n / 2번 수행되므로 시간 복잡도는 O(n)이고, 사용하는 메모리는 인덱스 두 개뿐이므로 공간 복잡도는 O(1)입니다. R은 예외입니다. 먼저 문자열을 문자 코드 벡터로 읽어들이며, 이 과정에 O(n)의 비용이 듭니다.

알고리즘

left = 0으로 설정하고 right = n-1로 설정합니다.
left < right인 동안 s[left]와 s[right]를 비교합니다.
서로 다르면 false를 반환합니다.
그렇지 않으면 left에 1을 더하고, right에서 1을 뺀 다음 반복합니다.
포인터가 만나거나 교차하면 모든 쌍이 일치한 것입니다. true를 반환합니다.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

함정과 경계 사례

반복문은 짧으므로 실수는 경계 조건과 반환문에 있습니다.

한 쌍이 일치하자마자 true를 반환하는 것. abca는 바깥쪽 쌍은 통과하지만 안쪽 쌍에서 실패하므로, true는 반복문이 끝난 뒤에만 반환해야 합니다.
right를 n-1 대신 n에서 시작하는 것. 그러면 끝을 넘어 읽게 됩니다(C에서는 종료 '\0' 문자까지 읽습니다). Lua와 R에서는 인덱스가 1부터 n까지이므로, 그 언어들에서는 right를 n에서 시작합니다.
문자열을 주소로 비교하는 것. C에서 reversed == s는 두 포인터를 비교하며, 새로 복사한 문자열이라면 항상 거짓입니다. strcmp를 사용하세요.
반복문에서 result = result + ch로 역순 문자열을 만드는 것. 매 단계마다 지금까지의 문자열 전체를 복사하므로, 문자 50,000개에 대해 약 1.25 × 10^9회의 문자 복사가 발생합니다.
Swift 문자열을 정수로 인덱싱하는 것. 컴파일되지 않습니다. 자체 인덱스를 사용해 s.utf8을 순회하거나 문자를 배열에 복사하세요.

자주 묻는 질문4

문자열이 회문인지 어떻게 확인하나요?

첫 번째 문자를 마지막 문자와 비교하고, 두 번째 문자를 끝에서 두 번째 문자와 비교하는 식으로 가운데를 향해 진행합니다. 어느 한 쌍이라도 다르면 문자열은 회문이 아니며, 모든 쌍이 일치하면 회문입니다. 양쪽 끝에서 시작해 안쪽으로 이동하는 두 인덱스를 사용하면 한 번의 순회로 이를 수행할 수 있습니다.

추가 메모리 없이 회문인지 확인할 수 있나요?

맞습니다. 두 포인터 검사는 문자를 제자리에서 읽고 인덱스 두 개만 저장하므로 추가 공간을 O(1) 사용합니다. s를 뒤집은 문자열과 비교하는 방법은 더 짧게 작성할 수 있지만, n개의 문자로 이루어진 두 번째 문자열을 만듭니다.

회문 문자열을 확인하는 시간 복잡도는 얼마인가요?

길이가 n인 문자열에서는 O(n)입니다. 두 포인터 검사는 최대 n / 2번 비교하고 첫 번째 불일치에서 멈추므로, 첫 문자와 마지막 문자가 다른 문자열은 한 번 비교한 후 판별됩니다.

단일 문자는 회문인가요?

네. 한 글자는 양방향으로 읽어도 같으므로 답은 true입니다. 두 포인터 루프에서 left와 right는 모두 인덱스 0에서 시작하고, 루프는 실행되지 않으며, 함수는 true를 반환합니다.

Python

def isPalindrome(s):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "racecar"

기대값

true