[2024] day 44. 2108. Find First Palindromic String in the Array

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 13일 (화)
Leetcode daily problem

2108. Find First Palindromic String in the Array

https://leetcode.com/problems/find-first-palindromic-string-in-the-array/description/?envType=daily-question&envId=2024-02-13

Problem

문자열로 원소로 구성된 배열 words가 주어질 때, 배열을 탐색하면서 펠린드롬 조건에 해당하는 가장 첫번째 문자열을 반환한다.

팰린드롬 (문자열을 뒤집어도 같은 문자열인 것)

Solution

array

배열에 있는 문자열을 while문을 이용해서 탐색하는데 첫번째 인덱스와 마지막 인덱스로 left, right를 주어 왼쪽은 문자열 중간으로 +1씩 이동하고 마지막 인덱스 right는 -1씩 이동하면서 서로 문자열이 같은지 비교한다.
left보다 right가 커지는 즉, 중간지점까지 체크가 다 통과했다면 해당 문자열은 팰린드롬에 해당하므로 해당 문자열을 반환한다.
그 전에 확인하는 탐색 과정에서 문자열이 같지않으면 다음 문자열 탐색을 시작한다.
모든 문자열을 탐색했지만 팰린드롬이 나오지 않을 경우에는 ""를 리턴하도록 한다.

Code

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for word in words:
            left, right = 0, len(word)-1
            while left < right:
                if word[left] != word[right]:
                    break
                left +=1
                right -=1
            
            else:
                return word
        
        return ""
        

Complexicity

시간 복잡도

주어진 문자열을 탐색할 때 O(N)의 시간이 소요되고,
while 문으로 문자열의 앞(왼쪽),뒤(오른쪽) 인덱스로 중간까지 문자열을 좁혀가면서 문자열이 같은지 아닌지에 대한 탐색을 수행하므로 O(2/N)이 소요된다.
그러므로 해당 코드가 수행하는 총 시간 복잡도는 O(N) 이다.

공간 복잡도

따로 공간을 사용하지 않으므로 공간 복잡도는 O(1)이다.

---

어이없게도 easy 문제라서 저렇게 구구절절 안써도 되는 것이었다.
그냥 word를 역순으로 만드는 슬라이싱으로 진행하면 되는 것이었다.
해당 코드도 시간복잡도가 O(N)이고, 공간복잡도가 O(1) 이기 때문이다..

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for word in words:
            if word == word[::-1]:
                return word

        return ""