Leetcode 5번 문제 풀이

개요

Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다.

 

문제 : 5. Longest Palindromic Substring

주어진 문자열 내에서 팰린드롬인 문자열을 찾아 반환해야 함.

 

풀이1 : Brute force

설명

Brute force(무차별 대입) 방식으로 풀 경우, 문자열 내 모든 문자마다 접근해서 팰린드롬인지 확인하여야 한다. 이 경우 시간 복잡도는 O(N^3) 이 나온다

 

** 시간 복잡도가 O(N^3) 인 것은 루프로 각 문자마다 접근을 하고, 팰린드롬인지 검사를 위해 이중 루프를 돌기 때문이다. (이중 루프를 어떤 방식으로 도는지에 대해선 정확히 모르고, 좀 더 자료조사가 필요)

 

그러므로 무차별 대입보다 좀 더 나은 방법이 필요하다.

 

다른 방법으로 DP(동적 계획법), Manchester's 알고리즘 등이 있지만 이 중 중앙에서 탐색하는 방법을 알아본다.

풀이2 : Expand from center

설명

우선 방법에 대해서 개략적인 설명을 예와 함께 살펴본다.

 

 

위 문자열이 팰린드롬인지에 대해서 검사를 하기 위해, 중앙에 있는 문자 e 에서부터 각각 왼쪽, 오른쪽 으로 뻗어가며 서로 같은 문자인지 경계전까지 반복적으로 검사를 한다. 검사가 끝나면 팰린드롬 문자열의 길이를 반환한다.

이 때 팰린드롬 문자열의 케이스는 중간지점에 문자가 있는 케이스와 없는 케이스 두 가지가 있는 것에 유의한다.

(ex. 중간지점 O : racecar, 중간지점 X : aabbaa)

 

문제에 적용하면 다음과 같다

 

팰린드롬 검사 함수

• 팰린드롬 문자열의 중앙에서 Left(좌), Right(우)로 뻗어나갈 인덱스를 선언한다.
  • Left는 문자열의 처음까지, Right는 문자열 끝까지 가도록 범위를 지정한다.
  • Left와 Right가 같은 문자인지 비교한다.
  • 반복 루프가 끝이나면 팰린드롬 문자열의 길이를 반환하는데 이는 Right - Left - 1를 통해 구한다.
    -1을 추가로 하는 이유는 증감연산자를 사용하므로 구하려는 처음, 끝 인덱스보다 더 값이 증감되기 때문에 이를 조정하기 위함임. 

메인함수

• 만약 문자열이 null이거나 0보다 작다면 빈 문자열을 반환한다
• 팰린드롬 문자열의 Start(처음)과 End(끝) 인덱스를 선언한다
• 각 문자마다 루프를 돈다
  • 이 때 중간지점에 문자가 있는 팰린드롬 케이스에 대해서 팰린드롬 검사함수를 실행하여 길이를 저장하고 좌우 인덱스는 현재 인덱스( i )를 동일하게 넣는다
  • 문자가 없는 팰린드롬 케이스에 대해서 검사함수를 실행할 때 인자로 현재 인덱스 ( i )와 현재 인덱스 + 1 ( i + 1 )을 인자로 넣는다 
    • 이 경우 중앙지점에서 양측이 대칭적으로 일치하기 때문에 현재 인덱스와 그 다음 인덱스를 비교함으로써 확인이 가능
  • 두 케이스 중 더 긴 길이를 저장하고, 그 길이값으로 팰린드롬 문자열의 시작과 끝 인덱스를 구한다
    • start 는 현재 인덱스 - (문자열 길이 - 1) / 2 로 구한다. 현재 인덱스는 중간에 위치했으므로 문자열 길이에서 반으로 나눠서 빼줘야지만 처음 인덱스를 구할 수 있음
      • 나누기 2 를 했을 때 값에 따라 소수점 값이 나올 때가 있음. 이를 정수형으로 바꿔주기
    • end 는 현재 인덱스 + 문자열 길이/2 로 구한다
      
      • 마찬가지로 나누기 2 를 했을 때 값에 따라 소수점 값이 나올 때가 있으므로 정수형으로 바꿔주기
    • start, end 인덱스를 구할 때 각각 연산이 조금씩 다른 이유는 알맞은 팰린드롬 문자열 인덱스를 구하기 위해서이다. 정확한 이유는 좀 더 찾아봐야 할 것 같다
• 구한 start, end 인덱스를 substring 함수에 넘겨주어 팰린드롬 문자열을 구한다 
  • end에 1을 더하는 이유는 substring 함수가 지정된 종료 인덱스의 직전까지의 부분 문자열만을 반환하므로 구한 end 인덱스에 1을 더 더해줘야지만 정답을 제대로 구할 수 있음

코드

이 때 시간 복잡도는 O(n^2) 가 되고 공간 복잡도는 O(1)이 나온다.

 

소감

팰린드롬 문자열은 몇년 전에 몇번 풀어봤지만 지금 다시 풀어보니 잘 풀리지 않았다. 풀이를 보니 다시금 생각이 났고 헷갈렸던 것은 인덱스와 문자열 메서드 사용과 관련해 정수를 더해주고 빼는 부분이 이해가 잘 안되서 시간이 들었다. 이렇게 인덱스에 숫자를 빼주거나 더하는 부분이 이해안될때는 직접 연습장에 코드를 디버깅한다고 생각하면 해결이 되었다. 다음부턴 이해가 안될 때는 연습장에 코드를 돌려보면서 이해속도를 늘릴 수 있도록 해야지

 

출처

문제풀이 :

https://www.youtube.com/watch?v=y2BD4MJqV20&t=778s