-
[프로그래머스 2단계] 알고리즘 27. 가장 긴 팰린도롬24년 11월 이전/레거시-알고리즘(3) 2018. 4. 13. 12:09반응형
문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)
알고리즘 27. 가장 긴 팰린도롬
앞뒤를 뒤집어도 똑같은 문자열을 palindrome이라고 합니다. longest_palindrom함수는 문자열 s를 매개변수로 입력받습니다. s의 부분문자열중 가장 긴 palindrom의 길이를 리턴하는 함수를 완성하세요. 예를 들어 s가
토마토맛토마토
이면 7을 리턴하고토마토맛있어
이면 3을 리턴합니다.def longest_palindrom(s):# 함수를 완성하세요return 0# 아래는 테스트로 출력해 보기 위한 코드입니다.print(longest_palindrom("토마토맛토마토"))print(longest_palindrom("토마토맛있어"))
풀이:이전에 팰린도롬 문제를 문자열을 그대로 뒤집어서 비교하는 코드로 푼 것을 기억하자 파이썬으로 다음과 같이 표현할 수 있다.
s == s[::-1]다른 언어와 달리 굉장히 간편하게 표현된다. 문자열을 다루는데는 파이썬만한 언어는 없다고 생각하는 바이다. 이제 문자열 중 부분 문자열 중 가장 긴 팰린도롬을 찾으면 된다. 나는 순차적으로 이 문제를 풀었다. 알고리즘은 다음과 같다.
- 문자열 첫 문자부터 끝 문자까지 팰린도롬을 찾는다.
- 각 문자에 대해서 문자열 끝 위치부터 문자의 위치까지 차례로 부분 문자열이 팰린도롬인지 판단한다
- 찾은 팰린도롬에 대해서 최대 길이를 계속 갱신해준다.
대충 설명만 들어서는 명확하지 않는데 예제를 보면 이해가 더 쉽게 될 것이다. 예를 들어 "토마토맛있어"라는 문자열이라면 다음과 같이 탐색한다.
첫 위치 토
토마토맛있어 -> 팰린토롬(X)
토마토맛있 -> 팰린토롬(X)
토마토맛 -> 팰린토롬(X)
토마토 -> 팰린토롬(O) -> 3저장
두번째 마
마토맛있어 ->팰린토롬(X)
마토맛있 ->팰린토롬(X)
마토맛 ->팰린토롬(X)
마토 ->팰린토롬(X)
마 ->팰린토롬(O) -> 1 저장
세번째 토
....
이제 필자의 의도를 정확히 알아차릴거라 생각한다. 핵심은 이중 반복이다. 코드를 보며 이해해보자. 나의 코드는 다음과 같다.
def longest_palindrom(s):max = 0 #문자열 최대 길이를 저장할 변수for i in range(0, len(s)): #첫 위치부터 끝 위치까지 문자열을 순회for j in range(len(s), i, -1): #문자열 끝에서부터 탐색 문자 위치까지 거꾸로 부분 문자열 탐색if s[i:j] == s[i:j][::-1]: #부분문자열 i ~ j가 팰린도롬이라면max = (j - i) if (j - i > max) else max #그 길이가 최대라면 갱신한다. j-i = len(s)break #부분 문자열은 끝에서부터 검사하기 때문에 찾는 즉시 그 길이가 최대이다.return max주석과 하께 읽으면 더 이해가 잘 갈 것이다. 이렇게만 하면 심심하기 때문에 재귀문으로 바꿔보겠다. 잘 짜여진 반복문은 재귀문으로 쉽게 바꿀 수 있다. 여기서 반복적으로 하는 일이 다음과 같이 두가지가 있다.
- 먼저 문자열이 팰린도롬인지 판단한다.
- 맞다면 최대 길이를 갱신한다. 아니라면 문자열 길이를 줄인다.
이제 한 번 바꿔보겠다. 코드는 다음과 같다.
def longest_palindrom_rec(s):return len(s) if s == s[::-1] else max(longest_palindrom(s[:-1]), longest_palindrom(s[1:]))여기서 길이를 갱신하는 코드는 else max(...) 부분이다. 첫 번째 인자는 문자열을 끝부터 줄인 부분 문자열들의 결과를 찾고 두 번째 인자는 시작 위치부터 줄인 부분 문자열들의 결과를 탐색한다. 이제 2단계 문제도 다 풀었다. 2단계의 11문제를 다 푼 자신에게 박수! 다음부터 3단계에 돌입한다.
728x90'레거시 > 레거시-알고리즘(3)' 카테고리의 다른 글
[프로그래머스 3단계] 알고리즘 29. 멀리 뛰기 (0) 2018.04.17 [프로그래머스 3단계] 알고리즘 28. N개의 최소 공배수 (0) 2018.04.16 [프로그래머스 2단계] 알고리즘 26. 2016년 (0) 2018.04.12 [프로그래머스 2단계] 알고리즘 25. 이상한 문자 만들기 (0) 2018.04.11 [프로그래머스 2단계] 알고리즘 24. 행렬의 곱셈 (0) 2018.04.10