[파이썬] JottoScore, SubSequence, LCS 구현

파이썬으로 처음 짠 코드

jotto score나 subsequence는 그다지 어렵지 않았으나

Longest Common Subsequence는 해결방법 자체가 잘 이해가 되지 않았다.

구글링한 결과 알고리즘은 찾았고 동적 프로그래밍이란 것도 얼핏 이해가 되었지만,

트래킹테이블이 왜 그렇게 만들어지는 것인지를 모르겠다. (이것은 한가할 때 도전해보기로 하고...)

찾아낸 알고리즘을 코드로 옮겨보았다.

이 과정 역시도 만만하지는 않았으니...

파이썬에 익숙하지 않은 점도 있었고, 인덱스가 여기저기 나오다 보니 많이 어지럽다...

그래서 주석은 물론이고, 최대한 메소드나 변수명을 용도를 알기 쉽게 

그리고 Magic Number를 줄이려 노력하였다.

# -*- coding: EUC-KR -*-

def jottoScore(start, end):

    score = 0  # jotto 점수

    resultOfSearch = None  # 검색된 두번째 문자열의 인덱스

    

    for i in range(len(start)):  # start 문자열의 길이만큼 반복

        resultOfSearch = end.find(start[i])  # end에서 start[i]의 문자 하나를 검색

        if(resultOfSearch > -1):

            score += 1  # 문자가 존재한다면 점수를 증가시키고

            end = end[0:resultOfSearch] + end[resultOfSearch + 1:]  # end 문자열에서 다시 검색이 되지 않도록 빼냄

    return score

def subseq(start, end):

    lastInx = -1  # find 메소드로 검색한 결과(인덱스)

    rShift = 1  # Right Shift 값

    if(start == ''):  # 공백은 참으로 처리

        return True

    for i in range(len(start)):  # start 문자열의 길이만큼 반복

        resultOfSearch = end[lastInx + rShift:].find(start[i])  # end 문자열에서 문자하나를 검색(지정한 위치에서 끝까지)

        if(resultOfSearch == -1):  # 검색실패

            return False

        else:

            lastInx += resultOfSearch  # 결과값 보정

    return True

def createLcsTrackingTable(start, end):

    duplicationValue = 1  # 중첩된 문자일 때는 1을 더함

    moveInx = 1  # 인덱스 이동

    sLength = len(start) + 1

    eLength = len(end) + 1  # 디폴트라인(값이 0)을 추가하여 길이가 증가

    trackingTable = [[0] * eLength for x in range(sLength)]  # 테이블 초기화

    

    for row in range(1, sLength):  # 디폴트라인은 무시하고 반복문 시작

        for col in range(1, eLength):

            if(start[row - moveInx] == end[col - moveInx]):  # 테이블에서 서로 중첩되는 문자가 발견된 경우

                

                # 왼쪽 대각선 방향의 값과 1을 합함

                trackingValue = trackingTable[row - moveInx][col - moveInx] + duplicationValue

                # 해당 인덱스 오른쪽과 아래쪽의 값을 모두 변경

                for inx in range(row, sLength):

                    tempTV = trackingValue  # 계산값 보존

                    for jnx in range(col, eLength):

                        if(tempTV >= trackingTable[inx][jnx]):  

                            trackingTable[inx][jnx] = tempTV

                        else : 

                            tempTV = trackingTable[inx][jnx]  # 현재값이 계산값보다 더 큰 경우

    return trackingTable

def pointTo(trackingTable, currentIndex):  # 트래킹 방향 계산

    row = currentIndex[0] - 1

    col = currentIndex[1] - 1  # 바운더리에 맞게 값 조정

    

    # 현재 인덱스 기준으로 위쪽 인덱스의 값이 같으면 위로(인덱스 감소)

    if(trackingTable[row][col] == trackingTable[row - 1][col]):

        while True: 

            currentValue = trackingTable[row][col]

            if(currentValue == trackingTable[row - 1][col]):  # 윗행(row-1)의 값과 현재값을 비교 

                row -= 1

            else:

                break

    

    # 왼쪽 인덱스의 값이 같으면 왼쪽으로 계속 진행 (인덱스 감소)

    if(trackingTable[row][col] == trackingTable[row][col - 1]):

        while True: 

            currentValue = trackingTable[row][col]

            if(currentValue == trackingTable[row][col - 1]):  # 왼쪽열(col-1)의 값과 현재값을 비교 

                col -= 1

            else:

                break

    # 모두 다르면 (작으면) 왼쪽 대각선 방향으로 진행하고

    # 해당 인덱스를 반환

    # 대각선으로 이동했을 때 리턴

    return [row, col]

def backTracking(trackingTable, end):

    baseInx = 1  # 백트래킹 완료 시의 인덱스

    lSubSeq = ""

    currentIndex = [len(trackingTable), len(trackingTable[0])]  # 테이블의 마지막 인덱스 (길이)

    while(True):

        currentIndex = pointTo(trackingTable, currentIndex)

        col = currentIndex[1]

        

        lSubSeq = end[col - 1] + lSubSeq  # Longest Common Subsequence 생성

        if(currentIndex[0] == baseInx):

            break

    return lSubSeq

    

def LCS(start, end):

    if(len(start) == 0 or len(end) == 0):

        return ''  # 빈 문자열일 경우

    

    trackingTable = createLcsTrackingTable(start, end)

    return backTracking(trackingTable, end)

    

# unit tests

import unittest

class ModuleTest(unittest.TestCase):

    def testJotto1(self):

        self.assertEqual(jottoScore('diner', 'syrup'), 1)

    def testJotto2(self):

        self.assertEqual(jottoScore('geese', 'elate'), 2)

    def testJotto3(self):

        self.assertEqual(jottoScore('gattaca', 'aggtccaggcgc'), 5)

    def testJotto4(self):

        self.assertEqual(jottoScore('gattaca', ''), 0)

    def testSubseq1(self):

        self.assertEqual(subseq('', 'cataga'), True)

    def testSubseq2(self):

        self.assertEqual(subseq('ctg', 'cataga'), True)

    def testSubseq3(self):

        self.assertEqual(subseq('ctg', 'tacggta'), False)

    def testSubseq4(self):

        self.assertEqual(subseq('aliens', 'always frighten dragons'), True)

    def testSubseq5(self):

        self.assertEqual(subseq('trogdor', 'that dragon is gone for good'), False)

    def testLCS1(self):

        self.assertEqual(LCS('human', 'chimp'), 'hm')

    def testLCS2(self):

        self.assertEqual(LCS('gattaca', 'tacgaacta'), 'gaaca')

    def testLCS3(self):

        self.assertEqual(LCS('wow', 'whew'), 'ww')

    def testLCS4(self):

        self.assertEqual(LCS('', 'whew'), '')

    def testLCS5(self):

        self.assertEqual(LCS('abcdefgh', 'efghabcd'), 'abcd')

if __name__ == "__main__":

    unittest.main()