[HackerRank][Python3] Common Child

Problem :

https://www.hackerrank.com/challenges/common-child/problem

My Solution :

#!/usr/bin/env pypy3


def commonChild(s1, s2):
    n = len(s1)
    memo = [[0]*(n+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(n):
            if s1[i] == s2[j]:
                memo[i+1][j+1] = memo[i][j] + 1
            else:
                memo[i+1][j+1] = max(memo[i][j+1], memo[i+1][j])
    return memo[n][n]


s1, s2 = input(), input()
result = commonChild(s1, s2)
print(result)

Comment :

이 문제는 아무리 노력을 해봐도 Python3 (CPython) 로는 일부 Test Case의 Timeout을 넘지 못했다. 하지만 동일 코드를 Pypy3로 실행해보면 통과를 한다. Test Case 5를 예로 들면 아래와 같이 거의 30배에 가까운 엄청난 성능 차이를 보인다. 그동안 별 생각없이 CPython을 사용했는데 Pypy로 갈아타야 하는 것인가...

[root@CentOS7 ~]# time python3 commonChild.py
1417

real	0m14.191s
user	0m14.064s
sys	0m0.098s
[root@CentOS7 ~]# time pypy3 commonChild.py
1417

real	0m0.685s
user	0m0.506s
sys	0m0.070s