[Leetcode 아주 상세한 문제풀이] 647. Palindromic Substrings – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 647번 문제 Palindromic substrings 다.

우선 문제를 살펴보자.

 

리트코드 647번 문제 Palindromic substrings 링크

https://leetcode.com/problems/palindromic-substrings/

Palindromic Substrings - LeetCode

 

Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.

Example 1:
Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:
Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
 
Constraints:
1 <= s.length <= 1000
s consists of lowercase English letters.

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 문자열 s가 주어진다. 이때 문자열 s 내에 존재하는 substring 중 palindromic한 substring이 몇개인지 찾아내라는 것이다. 이 문제를 해결하기 위해서는 우선 palindrome의 정의해 대해 알아야 한다. Palindrome 이란 앞으로 읽어도 뒤로 읽어도 똑같은 문자다. 대표적으로 이상한 변호사 '우영우'를 꼽을 수 있다. 앞으로 읽어도 뒤로 읽어도 우영우 이기 때문이다.

이 문제에서는 palindromic한 substring을 '모두' 찾아내야 한다. 문제 예시 2번에서 보는 것처럼 aaa 라는 문자열이 주어졌을 때 a 각 문자가 스스로 palindrome이 될 수도 있다. 더불어 aa 역시 palindrome이 되는데 이때 aa는 두 번 카운트 됨을 유의해야 한다. 그 이유는 substring은 순서를 갖기 때문인데, 주어진 문자열의 첫번째와 두번째 aa 그리고 두번째와 세번째 aa는 다른 substring으로 인식되기 때문이다. 이제 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위하여 우리는 palindrome의 성질에 대해 정확히 이해를 해야 한다.

앞으로 읽어도 뒤로 읽어도 똑같다는 얘기는 가운데 지점을 중심으로 좌우가 동일하다는 것이다.

예를 들어 ABC라는 문자가 palindrome인지 판단한다고 생각해보자.

우리는 우선 ABC의 가운데 지점인 B를 선택한다.

그리고 B를 기준으로 왼쪽으로 한 칸 오른쪽으로 한 칸 탐색을 한다.

이 문자열이 palindrome 이라면 B를 기준으로 양 옆이 동일한 문자여야 한다.

따라서 첫번재 탐색에서 왼쪽에 위치한 문자 (A)와 오른쪽에 위치한 문자 (C)가 다르므로 이 문자열은 palindrome이 아님을 알 수 있다.

또 하나 고려해야 할 점은 palindrome인지 아닌지 판별해야 하는 문자열 길이가 홀수인지 짝수인지 확인해야 한다.

위의 예시와 같이 ABC 처럼 문자열 길이가 홀수인 경우 가운데 지점을 중심으로 양쪽을 동일하게 탐색할 수 있다.

하지만 ABCD 처럼 문자열 길이가 짝수인 경우 가운데에 위치한 B와 C가 서로 같은지 판단 후 양쪽으로 탐색을 진행해야 한다.

이 경우 B와 C가 다르므로 더 이상 탐색을 진행할 필요가 없다.

위의 두 가지 전략을 고려하여 주어진 문자열을 처음부터 하나씩 탐색하며 palindrome인지 판단하면 된다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

문자열을 입력받기 위한 함수를 정의해 준다. (line 1)

추가로 가운데 지점을 중심으로 양 옆을 탐색해 palindrome 인지 판별하는 함수를 정의해 준다. (line 2)

Palindrome 개수를 카운트 하기 위한 변수를 하나 만들어 준다. (line 3)

이제 가운데 지점을 중심으로 탐색을 진행할 것이다.

탐색하는 위치가 문자열 안쪽에 있고 (left >=0 and right <len (s)) 탐색하는 문자가 서로 같다면 (line 4)

Palindrome 카운트를 하나 올려주고 다음 탐색을 위해 left 포인터는 왼쪽으로 right 포인터는 오른쪽으로 옮겨준다. (line 5)

이 과정은 문자열 길이를 벗어나거나 혹은 palindrome이 아님이 확인될때까지 반복한다.

이 과정을 마치고 나면 palindrome 이 몇개인지 count에 저장되기 때문에 이를 리턴하면 된다. (line 8)

문자열 전체에 존재하는 palindrome 이 몇 개 인지 카운트 하기 위한 변수를 만들어 준다. (line 10)

이제 문자열의 첫번째 문자부터 하나씩 탐색을 할 것이다. (line 11)

이때 중요한 것은 길이가 홀수인 palindrome과 짝수인 palindrome을 각각 구해 총 합을 구해야 한다는 것이다.

예를 들어 "ABBA"라는 문자열을 생각해 보자.

이때 길이가 홀수인 palindrome 은 A, B 두 개가 존재한다.

즉, 각 문자를 기준으로 양 옆으로 탐색을 하다보면 홀수 길이를 가진 palindrome 은 두 개 밖에 찾을 수 없다.

하지만 우리는 ABBA에라는 길이가 짝수인 palindrome 도 존재함을 알 수 있다.

이는 한 문자를 기준으로 양 옆을 탐색하는 방식으로는 찾을 수 없다.

따라서 우리는 길이가 홀수와 짝수인 palindrome의 개수를 각각 구해 총 합을 구해줘야 한다. (line 13, 15)

모든 탐색 과정을 마치고 나면 우리가 찾고자 하는 총 palindrome 개수를 리턴하고 종료한다. (line 17)

 

 

문제 풀이 코드

def count_palindromic_substrings(s):
    def count_palindromes_around_center(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
 
    total_palindromes = 0
    for i in range(len(s)):
        # Count odd length palindromes centered at s[i]
        total_palindromes += count_palindromes_around_center(i, i)
        # Count even length palindromes centered between s[i] and s[i+1]
        total_palindromes += count_palindromes_around_center(i, i + 1)
 
    return total_palindromes
 
# Test the function with the provided examples
print(count_palindromic_substrings("abc"))  # Output: 3
print(count_palindromic_substrings("aaa"))  # Output: 6
 

 

 

관련 문제

리트코드 3번 Longest substring without repeating characters 문제풀이

리트코드 5번 Longest palindromic substring 문제풀이

리트코드 20번 Valid parenthesis 문제풀이

리트코드 49번 Group anagram 문제풀이

리트코드 76번 Minimum window substring 문제풀이

리트코드 125번 Valid palindrome 문제풀이

리트코드 242번 Valid anagram 문제풀이

리트코드 424번 Longest repeating character replacement문제풀이

 

 

647. Palindromic Substrings