개요
| LeetCode | |
| 문제 명 | Longest Palindromic Substring |
| 난이도 | Medium |
| 체감 난이도 | Medium |
| 풀이 시간 | 1시간 20분 정도 |
문제 설명
Given a string s, return the longest palindromic substring in s.
문자열 s가 주어지면, 가장 긴 palindromic 문자열을 리턴하라.
여기서 palindromic 문자열을 한국어로 표현하기가 애매한데, 쉽게 말하자면 반으로 접었을 때 똑같은 모양이 나오는 데칼코마니라고 생각하면 된다.
입출력 예시
| 입출력 예시 1 | |
| 입력 값 | s = "babad" |
| 기대 값 | bab || aba |
| 설명 | bab, aba은 길이가 동일하므로 둘 중 아무거나 상관없음. |
제약 조건
- 1 <= s.length <= 1000
- 입력 값은 문자와 숫자로만 구성됨.
풀이
본 문제가 상당한 난이도를 요구하는 문제는 아니었지만, 코딩 테스트를 오랜만에 다시 하는 거라 여러 방면으로 생각을 많이 했던 거 같다.
처음 이 문제를 보자마자 "아, 이건 스택을 써야겠다"라고 생각했고, 그렇게 두 번 정도의 다른 알고리즘을 가진 코드를 작성했다.
음,, 스택으로 구현하니 "bananas" 입력이 들어왔을 때, ana가 리턴된다. anana가 리턴되어야 하는데 말이다.
ana도 palindromic 문자열이기 때문에 ana 이후 stack은 초기화되어 버린다.
분명 스택을 써서 모든 예외를 피하는 코드가 있겠지만 코드 효율성 검사에도 통과를 해야 한다고 생각하니, 출제자가 의도한 문제 풀이가 무엇일까 생각했다.
카페에 앉아서 생각하는데 번뜩이며 아이디어가 스쳐 지나갔다.
- 문자열 슬라이싱을 활용하자
- 이걸 기가 막히게 써먹어보자
비록 for문을 두 번이나 쓴 건 찝찝하지만, 내가 생각해 낸 최선을 방법이었다.
실패한 코드 1
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) == 1 or len(set(s)) == 1: return s
stack = []
for index, c in enumerate(s):
# init
if not stack:
stack.append(index)
continue
# branch
if s[stack[-1]] == c:
stack = stack[:-1]
continue
if len(stack) >= 2 and s[stack[-2]] == c:
stack = stack[:-2]
continue
if c not in stack:
stack.append(index)
return self.getResult(s, stack) if stack else s
def addChar(self, string:str, char: str) -> str:
return string + char
def getResult(self, s:str, stack:list) -> str:
if len(stack) == len(s): return s[0]
for idx in stack:
s = s[:idx] + "!" + s[idx + 1 :]
return s.replace("!", "")
스택을 사용하며 하나 또는 둘 뒤에 있는 문자와 일치하면 스택을 해당 문자열을 빼고 업데이트해 준다.
스택에는 palindromic 문자열이 아닌 문자열의 인덱스가 들어있다.
다시 생각해 보니 저건 뭐 하는 코드일까 라는 생각이 든다.
실패한 코드 2
class Solution:
def isPalindrome(self, s: str) -> bool:
for i in range(len(s) // 2):
if s[i] != s[-(i + 1)]:
return False
return True
def longestPalindrome(self, s: str) -> str:
if len(s) == 1: return s
if len(set(s)) == 1: return s
result = []
for i in range(len(s)):
init = True
stack = []
string = ""
for j in range(i, len(s)):
if init:
stack.append(s[j])
string += s[j]
init = False
continue
if not stack:
if self.isPalindrome(string):
result.append(string)
if string and string[-1] == s[j]:
string += s[j]
continue
stack.append(s[j])
elif stack[-1] == s[j]:
stack = stack[:-1]
elif len(stack) >= 2 and stack[-2] == s[j]:
stack = stack[:-2]
else:
stack.append(s[j])
string += s[j]
if not stack and self.isPalindrome(string):
result.append(string)
elif len(stack) == len(s):
result.append(string[0])
return sorted(result, key = len, reverse=True)[0]
이건 string 변수와 result 배열을 사용해서 조건에 부합하는 모든 string을 result에 넣는다.
이 방식은 꽤 나쁘지 않다고 생각했지만, "bananas"와 같은 문자열을 예외처리 하기가 곤란하다.
코드를 더 추가하면 해결할 수 있겠지만, 이렇게 긴 코드는 내가 싫다.
최종 제출코드
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) == 1: return s # 문자열의 길이가 1이면 그대로 반환
result = "" # 가장 긴 회문을 저장할 변수 초기화
for i in range(len(s)): # 문자열의 각 문자에 대해 반복
for j in range(len(s) - 1): # 시작 인덱스부터 끝 인덱스까지 부분 문자열 생성
string = s[i : len(s) - j] # 부분 문자열 생성
if self.isPalindrome(string): # 회문인지 확인
if len(string) > len(result): # 현재 회문이 저장된 회문보다 긴 경우
result = string # 결과 갱신
break # 내부 루프 종료
return result # 가장 긴 회문 반환
def isPalindrome(self, s: str) -> bool:
for i in range(len(s) // 2): # 문자열의 절반까지 반복
if s[i] != s[-(i + 1)]: # 대응되는 문자가 같지 않은 경우
return False # 회문이 아님
return True # 모든 문자가 대응되면 회문임
위는 테스트에 통과된 코드이다.
이중 for문은 아직까지 매우 거슬리지만, 실제로 메모리 사용량은 양호한 편이라 약간은 만족하고 있다.
Runtime은 매번 다르게 나온다.
똑같은 코드임에도 한 번은 4850ms가 나왔고, 5350ms, 그리고 사진과 같이 7015ms가 나왔다.
그래서 Memory 효율을 조금 더 신경 쓰면 좋을 거 같다.
내 코드는 16.46MB를 사용했고, 메모리 효율성에서 94.83% 사용자를 이겼다.
위 코드에 대한 설명은 주석으로 정말 자세하게 적어보았다.
회고
문제를 나 혼자 생각하고 고민하며 해결하고 난 후에 다른 블로거가 작성한 모범 답변을 봤다.
전혀 생각하지 못한 방식으로 문제를 풀었던데, 대단한 거 같다.
이번 문제는 나름 재밌게 푼 거 같다!
'코딩테스트 > LeetCode' 카테고리의 다른 글
| [LeetCode] Reverse Integer 풀이 및 후기 (0) | 2024.06.21 |
|---|---|
| [LeetCode] Zigzag Conversion 풀이 및 후기 (1) | 2024.06.16 |