[BOJ 6574] 백준 새로운 과일 파이썬

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 백준의 6574번 문제 새로운 과일이다.

https://www.acmicpc.net/problem/6574

 

LCS를 잘 모른다면 감조차 잡기 힘들 수 있는 문제이다.

 

LCS에 대해선 이 분의 글이 참 좋았다. (글 잘 적는 사람 부러워요)

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

 

해결 과정

 

 

이 문제를 한 마디로 두 단어 사이 최장 공통 부분수열 파악하고 공통 부분수열 사이의 단어들을 알맞은 위치에 집어넣는 문제이다. 알맞은 위치라는 말이 모호하게 들릴 수 있는데

 

apple과 peach를 예로 이 경우 최장 공통 부분수열은 pe 가 될 것이다. 

그리고 이 두 단어를 합칠 때 각각 p와 e앞의 문자들은 합쳐진 단어의 p와 e의 앞에 들어가고

p와 e의 뒤에 있는 문자들은 합쳐진 단어에서도 그래야한다. 그래서 알맞은 위치라 말하였다.

 

 

문제에 대한 파악은 충분할 듯 한데 이걸 어떻게 풀어낼지는 또다른 문제이다.

기본적으로 LCS는 2차원 배열(테이블)로 풀어낼 수 있고 가장 끝 좌표 (last_x, last_y)에서부터 0인 값을 찾을때까지 역으로 탐색하여 최장 공통 부분수열을 알아낼 수 있다. 필자는 재귀적으로 최장 공통 부분수열을 알아냈고

구체적으로 서술하자면 최장 공통 부분수열의 원소 하나 하나를 찾을때마다 그 이전 원소에서 지금 찾은 원소까지의 경로 중 최장 공통 부분수열에 해당되지 않는 두 단어들의 값들을 일관성 있게 저장해 (왼쪽 단어가 더 앞에 오도록 ) 새로운 단어를 완성해갔다.

 

더 이상 설명해봤자 복잡하기만 할 것 같아 코드를 잘 해석해주길 바라겠습니다.

(사담이지만 글 잘 적는 사람들 대단해요. 그림도 멋진 거 넣고)

 

 

 

코드 전문

 

 

import sys  # lcs 사용, 0번대 인덱스에 0패딩을 줘서 인덱스 계산이 어려워요
        
def find_lcs_and_make_new_word(x, y, s, l_t_s, r_t_s): # x, y 최장 공통 부분수열을 찾기 위한 시작 좌표
    global lcs                                       # s는 새로 만들어질 단어

    if lcs[y][x] == 0: 
        s = rhs[0:y] + s
        s = lhs[0:x] + s
        return s

    if lcs[y][x-1] == lcs[y][x]:
        
        l_t_s = lhs[x-1] + l_t_s
        return find_lcs_and_make_new_word(x-1, y, s, l_t_s, r_t_s)
    elif lcs[y-1][x] == lcs[y][x]:
        
        r_t_s = rhs[y-1] + r_t_s
        return find_lcs_and_make_new_word(x, y-1, s, l_t_s, r_t_s)
    else:
        
        s = r_t_s + s
        s = l_t_s + s
        s = lhs[x-1] + s     
        return find_lcs_and_make_new_word(x-1, y-1, s, "", "")

while True:
    lcs = [[0 for _ in range(105)] for _ in range(105)]

    try:
        lhs, rhs  = sys.stdin.readline().split()

    except:
        break

    for i in range(1, len(rhs)+1):
        for j in range(1, len(lhs)+1):
            if rhs[i-1] == lhs[j-1]:
                lcs[i][j] = lcs[i-1][j-1] + 1
            else:
                lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
    
    ans = find_lcs_and_make_new_word(len(lhs), len(rhs), "", "", "")
    print(ans)

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.