Today I learned
2022/01/17
회고록
1/17
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
6장 문자열 조작
1. 이론
문자열에 관한 이론
문자열(String)이란 문자, 단어 등으로 구성된 문자들의 집합을 의미한다. 예를 들어 다음과 같은 것들이 문자열이다.
"Life is too short, You need Python"
"a"
"123"
위 문자열 예문을 보면 모두 큰따옴표(" ")로 둘러싸여 있다. "123은 숫자인데 왜 문자열이지?"라는 의문이 드는 독자도 있을 것이다. 따옴표로 둘러싸여 있으면 모두 문자열이라고 보면 된다.
2. 문제
가장 긴 팰린드롬 부분 문자열
가장 긴 팰린드롬 부분 문자열을 출력하라.
입력
"babad+"
출력
"bab"
- "bab" 외에 "aba"도 정답이다.
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters.
Accepted
1,649,065
Submissions
5,213,755
https://leetcode.com/problems/longest-palindromic-substring/
3. MySol
def longest_palindrome(target):
#palindrome 문자열을 저장할 리스트
palinList = []
#start 1씩 증가
for start in range(len(target)):
#end 포인터 -> 문자열 맨 끝으로 위치
end = len(target)
#start ~ end 까지 문자열 길이가 1보다 작으면 더이상 palindrome이 될 수 없으므로 끝냄
if end-start<=1:
break
#start지점은 고정되어있고, end 지점을 1칸씩 앞으로 이동시키며 문자열 case 비교
while (True):
isPalin = True
print('[시작!]')
print('start : ' + str(start) + ', end : ' + str(end))
n=target[start:end]
print('slice : ' + n)
#문자열 짝수, 홀수 구분 로직
odd_even_check = end-start
print('length : ' + str(odd_even_check))
if(odd_even_check%2==0):
#짝수
print('짝수')
odd_even_check = False
else:
#홀수
print('홀수')
odd_even_check = True
i=0
j=len(n)-1
# Target 문자열 내, 맨앞(i)과 맨끝(j)에서부터 한칸식 줄면서 palindrome 비교
while(True):
print('i : ' + str(i) + ", j : " + str(j))
if n[i]!=n[j]:
isPalin=False
break
i+=1
j-=1
if odd_even_check:
print('홀수 진입, odd_even_check : ' + str(odd_even_check))
# 홀수라면,
if i == j:
print('if 진입 : i : ' + str(i) + ', j : ' + str(j))
break
else:
if i == j+1:
break
#Palindrome인 경우, 리스트에 해당 문자열을 추가
if(isPalin):
print('isPalin : ' + str(isPalin))
palinList.append(n)
#end 1씩 감소
end-=1
if end-start<=1:
break
return palinList
if __name__ == '__main__':
n = "oihuyftrdrhrotatorjkuytrerfgh"
palinList = longest_palindrome(n)
maximum_length=max(palinList, key=len)
print('List : ' + str(maximum_length))책의 해답에서는 투포인터 방식을 이용한 solution이 있었으나, 아직 익숙치 않았던 나는 반복문으로 브루트포싱을 하여 해당 문제를 해결하였다.
내 방식은 최대치의 문자열 길이에서부터 범위를 좁혀오는 방식이라고 치면, 해답의 방식은 투 포인터를 좁은 범위에서 넓게 넓히는 방식으로 책에 있는 해답이 더 효율적이다.
4. 배운 점
-
palindrome 문자열이란, 앞에서 읽어도, 뒤에서 부터 읽어도 같은 문자열을 말한다. ex) rotator.
-
투포인터 : 두 포인터를 두고, 슬라이딩 윈도우 처럼 계속 앞으로 전진해 나간다. 이때, 포인터 사이에 들어온 문자열이 팰린드롬일 경우, 그 자리에 멈춰서서 좌우로 범위를 넓혀나간다.
5. 총평
머리아픈 반복문 훈련
