ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [프로그래머스 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]


    다른 언어와 달리 굉장히 간편하게 표현된다. 문자열을 다루는데는 파이썬만한 언어는 없다고 생각하는 바이다. 이제 문자열 중 부분 문자열 중 가장 긴 팰린도롬을 찾으면 된다. 나는 순차적으로 이 문제를 풀었다. 알고리즘은 다음과 같다.

    1. 문자열 첫 문자부터 끝 문자까지 팰린도롬을 찾는다.
    2. 각 문자에 대해서 문자열 끝 위치부터 문자의  위치까지 차례로 부분 문자열이 팰린도롬인지 판단한다
    3. 찾은 팰린도롬에 대해서 최대 길이를 계속 갱신해준다.

    대충 설명만 들어서는 명확하지 않는데 예제를 보면 이해가 더 쉽게 될 것이다. 예를 들어 "토마토맛있어"라는 문자열이라면 다음과 같이 탐색한다.


    첫 위치 토

    토마토맛있어 -> 팰린토롬(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


    주석과 하께 읽으면 더 이해가 잘 갈 것이다. 이렇게만 하면 심심하기 때문에 재귀문으로 바꿔보겠다. 잘 짜여진 반복문은 재귀문으로 쉽게 바꿀 수 있다. 여기서 반복적으로 하는 일이 다음과 같이 두가지가 있다.

    1. 먼저 문자열이 팰린도롬인지 판단한다.
    2. 맞다면 최대 길이를 갱신한다. 아니라면 문자열 길이를 줄인다.

    이제 한 번 바꿔보겠다. 코드는 다음과 같다.


    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
Designed by Tistory.