[파이썬] (level4) 땅따먹기 게임

문제

접근 방법

pre_dup : 이전(previous) 라인의 max값 중복 유무
cur_dup : 현재(current) 라인의 max값 중복 유무
pre_max_idx : 이전 라인의 max값 인덱스
cur_max_idx : 현재 라인의 max값 인덱스

경우의 수를 직접 만들어봐야 한다. 인덱스의 겹침 유무는 나중에 판단해도 된다.
max값이 리스트 내에 또 있는지가 중요하다. (즉, 중복 유무)


단, for문의 range는 0이 아니라 1 부터 시작한다고 가정한다.

• (1) pre_dup (O) cur_dup (O)
  5 12 12 3 <- 이전 라인
  13 13 12 3 <- 현재 라인

  • 이전 라인과 현재 라인 모두 max가 중복해서 존재하는 경우 현재 라인의 최대값을 더하면 된다.

• (2) pre_dup (O) cur_dup (X)
  5 12 12 3 <- 이전 라인
  3 13 7 1 <- 현재 라인

  • 이전 라인에 max가 중복해서 존재하는 경우, 현재 라인의 최대값을 더하면 된다.

• (3) pre_dup (X) cur_dup (O)
  5 13 7 1 <- 이전 라인
  3 8 8 1 <- 현재 라인

  • 현재 라인에 max가 중복해서 존재하는 경우, 현재 라인의 최대값을 더하면 된다.

• (4) pre_dup (X) cur_dup (X)
  11 12 10 9 <- 이전 라인
  1 8 1 1 <- 현재 라인

  • 이전 라인과 현재 라인의 max값의 인덱스 겹침 이 발생하면 비교가 필요하다.
  • 위 예제를 보면 이전 라인에서 두 번쨰로 큰 값을 선택하는 것이 현재 라인에서 더 큰 효용을 얻을 수 있다. 따라서 max 인덱스가 겹치면, 비교를 해봐야 한다.

나의 코드

def hopscotch(board, size):
    result = max(board[0])
    # 땅따먹기 게임으로 얻을 수 있는 최대 점수는?
    for row in range(1, size):
        pre_max = max(board[row-1])
        cur_max = max(board[row])
        sec_max = sorted(board[row])[-2]
        pre_max_idx = board[row - 1].index(max(board[row - 1]))
        cur_max_idx = board[row].index(max(board[row]))
        sec_large_idx = board[row-1].index(sorted(board[row-1])[-2])
        cmp_diff = (max(board[row - 1]) - sorted(board[row - 1])[-2]) < (max(board[row]) - sorted(board[row])[-2])
        pre_is_dup = True if max(board[row - 1]) in board[row - 1][pre_max_idx + 1:] else False
        cur_is_dup = True if max(board[row    ]) in board[row    ][cur_max_idx + 1:] else False

        if pre_is_dup and cur_is_dup:
            result += cur_max
        elif pre_is_dup and not cur_is_dup:
            result += cur_max
        elif not pre_is_dup and cur_is_dup:
            result += cur_max
        elif not pre_is_dup and not cur_is_dup:
            if pre_max_idx != cur_max_idx:
                result += cur_max
            elif pre_max_idx == cur_max_idx:
                if cmp_diff:
                    result = result - pre_max + sorted(board[row-1])[-2] + cur_max
                else:
                    result += sorted(board[row])[-2]
    return result

3일 걸려서 작성한 코드인데, 결론부터 말하면, 이 문제는 테스트케이스를 완벽하게는 통과하지 못한다. 얻어걸린 면이 있다. 코드도 깔끔하지 못하다.

좀 더 깔끔한 코드

def hopscotch(board, size):
    accum = [0] * len(board[0])

    for row in board:
        tmp = accum[:]
        for i in range(len(row)):
            accum[i] = row[i] + max(tmp[:i] + tmp[i+1:])

    return max(accum)

자기 자신의 index를 제외한 나머지 인덱스들 중에서 최대값을 찾아야 하므로
max(tmp[ : i] + tmp[i+1 : ])로 작성한 것이 인상적이다.
또한 max 연산 내에서 +를 활용했다는 것이 아름다웠다. 뭔가 테크닉적인 부분이 많이 들어가서 충분히 배울 가치가 있다고 생각한다.

배운 것

1. 변수에 if 문을 사용해 True / False 를 사용할 수 있다.

   • 아래 코드는 max가 리스트에 중복해서 존재하는지 검사하는 변수다.

   is_dup = True if max(board[row]) in board[row][cur_max_idx + 1:] else False
   

2. 리스트 내에서 두 번째로 큰 값에 접근할 수 있게 되었다.

   • sorted는 기존 리스트의 값을 변경하지 않는다는 것을 확실하게 깨우침(항상 sort와 긴가민가)
   • 응용해서 세 번째로 큰 값, 네 번째로 큰 값도 만들 수 있을 것이다.

   list = [7, 11, 3, 5, 8]
   sec_large = sorted(max(list))[-2]
   

3. 경우의 수를 따지는 문제에 좀 더 익숙해졌다.