프로그래머스 - 카드 게임 풀이 (python3)

프로그래머스 카드게임은 DP로 분류된 문제로, 설명은 여기서 볼 수 있고 풀어볼 수도 있다.

 

DP를 풀어본지 오래 돼서 풀어보려고 했으나 아이디어가 떠오르지 않아서 정답을 올려놓은 블로그 글을 참고했다.

그랬더니 DP를 푸는 방법에 대해 설명하는걸 보고 다시 DP에 공부했던 기억이 새록새록 떠올랐다.

다시 알게 된 김에 아래 3가지 방법 모두 구현해 보았다.

 

• Top-Down: 큰 문제들을 풀 때 작은 문제가 아직 풀리지 않았다면 작은 문제를 먼저 푸는 방식

  ex) 재귀함수, Memoization

• Bottom-Up: 작은 문제부터 차근차근 풀어나가는 방식

 

이 문제의 기본 아이디어는 다음과 같다.

 

i) 왼쪽 카드가 오른쪽 카드보다 크면, 오른쪽 카드를 버리고 점수를 높인다.
ii) 그렇지 않으면, 왼쪽만 버리는 방법과 오른쪽만 버리는 방법을 비교해 max를 찾는다.

 

재귀함수

재귀함수는 위의 아이디어를 직관적으로 코드로 옮기면 끝난다. 하지만 재귀함수가 그렇듯 많은 테스트 케이스에서 시간초과가 떴다.

def solution_recur(left, right):
    return recursive(left, right, 0, 0)

def recursive(left, right, l, r):
    if l == len(left) or r == len(right):
        return 0

    if left[l] > right[r]:
        return recursive(left, right, l, r+1) + right[r]
    else:
        return max(recursive(left, right, l+1, r), recursive(left, right, l+1, r+1))

 

Memoization

Memoization은 동일한 recursive 호출을 1번만 하도록 이미 계산한 값은 저장해 두고 가져다 쓰는 것이기 때문에 memo라는 배열을 사용했다.

하지만 정확성 테스트는 모두 통과했지만 효율성 테스트에서 런타임 에러가 났다. 아무래도 재귀호출 횟수 제한이 넘어가지 않았나 싶다.

def solution_memo(left, right):
    memo = [[-1]*len(left) for _ in range(len(right))]
    return memoization(memo, left, right, 0, 0)

def memoization(memo, left, right, l, r):
    if l == len(left) or r == len(right):
        return 0

    if memo[l][r] != -1: return memo[l][r]

    if left[l] > right[r]:
        memo[l][r] = memoization(memo, left, right, l, r+1) + right[r]
        return memo[l][r]
    else:
        memo[l][r] = max(memoization(memo, left, right, l+1, r+1), memoization(memo, left, right, l+1, r))
        return memo[l][r]

 

Bottom Up

마지막 Bottom up 방식은 비교하는 순서가 중요하다.

카드 게임의 핵심 아이디어에서 보면 왼쪽 카드 <= 오른쪽 카드 인 경우에 왼쪽 카드를 버리는 경우와 둘 다 버리는 경우 중에 max 값을 찾는다고 했다.

위의 재귀함수나 memoization 방식은 비교 대상인 왼쪽 카드를 버리는 경우(l+1, r)와 둘 다 버리는 경우(l+1, r+1)를 먼저 계산하기 때문에 결국 카드를 뒤집는 순서의 역방향으로 계산하며 올라가는 방식이다.

즉, 가장 먼저 계산되는 카드가 left[n-1], right[n-1]이고, 가장 나중에 계산되는 카드가 left[0], right[0]이다.

 

그래서 마찬가지로 Bottom up 방식도 카드를 뒤집는 순서의 역으로 채워야 한다.

def bottomUp(left, right):
    dp = [[0]*(len(left)+1) for _ in range(len(right)+1)]
    
    for l in range(len(left)-1,-1,-1):
        for r in range(len(right)-1,-1,-1):
        if left[l] > right[r]:
            dp[l][r] = dp[l][r+1] + right[r]
        else:
            dp[l][r] = max(dp[l+1][r+1], dp[l+1][r])

    return dp[0][0]

 

 

---

(+) 추가로, 정방향으로 채우면 왜 틀린 답이 나오는지 알아보았다.

 

아래 코드는 정방향으로 채우는 코드로, 이 코드를 제출하면 정확성 16번에서 실패로 뜬다.

def bottomUp(left, right):
    dp = [[0]*(len(left)+1) for _ in range(len(right)+1)]

    for i in range(1, len(left)+1):
        for j in range(1, len(right)+1):
            if left[i-1] > right[j-1]:
                dp[i][j] = dp[i][j-1] + right[j-1]
            else:
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])

    return dp[len(left)][len(right)]

 

 

두 알고리즘의 차이점은 [3,3,1],[7,7,1] 이나 [1, 1, 9, 1, 1, 1, 1], [8, 9, 1, 1, 1, 1, 1]의 테스트케이스에서 차이가 난다.

간단히 [3,3,1],[7,7,1] 테스트 케이스로 확인해 보면 다음과 같다.

 

 

 

정방향의 마지막 케이스는 1과 1이고, 숫자가 동일하기 때문에 max를 찾아야 한다.

그러므로 dp[3][3] = max(dp[2][2], dp[2][3])으로 1이 된다.

 

역방향의 마지막 케이스는 3과 7이고, 오른쪽 카드가 더 크기 때문에 max를 찾아야 한다.

그러므로 dp[0][0] = max(dp[1][1], dp[1][0])이기 때문에 0이 된다.