[SWEA][D3][#11806] 탐욕_베이비진 게임

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

0부터 9까지인 숫자 카드 4세트를 섞은 후 6개의 카드를 골랐을 때, 연속인 숫자가 3개 이상이면 run, 같은 숫자가 3개 이상이면 triplet이라고 한다.

게임을 시작하면 플레이어1과 플레이어 2가 교대로 한 장 씩 카드를 가져가며, 6장을 채우기 전이라도 먼저 run이나 triplet이 되는 사람이 승자가 된다.

두 사람이 가져가게 되는 순서대로 12장의 카드에 대한 정보가 주어졌을 때 승자를 알아내는 프로그램을 작성하시오. 만약 무승부인 경우 0을 출력한다.

예를 들어 9 9 5 6 5 6 1 1 4 2 2 1인 경우, 플레이어 1은 9, 5, 5, 1, 4, 2카드를, 플레이어2는 9, 6, 6, 1, 2, 1을 가져가게 된다.

이때는 카드를 모두 가져갈 때 까지 run이나 triplet이 없으므로 무승부가 된다.

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 각 줄에 0에서 9사이인 12개의 숫자가 주어진다.

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예제

입력

3
9 9 5 6 5 6 1 1 4 2 2 1
5 3 2 9 1 5 2 0 9 2 0 0
2 8 7 7 0 2 2 2 5 4 0 3

출력

#1 0
#2 1
#3 2

My Sol

def exchange(i, k):
    global checkArr

    if i == k:
        if check(checkArr):
            return 1
        return 0

    for j in range(i, k):
        checkArr[i], checkArr[j] = checkArr[j], checkArr[i]
        if exchange(i+1, k): return 1
        checkArr[i], checkArr[j] = checkArr[j], checkArr[i]
    return 0


def check(arr):
    l = len(arr)
    s = 0
    while l >= 3:
        if arr[s]+1==arr[s+1] and arr[s+1]+1==arr[s+2]: return 1
        if arr[s]==arr[s+1]==arr[s+2]: return 1
        l -= 1
        s += 1
    return 0


T = int(input())
for tc in range(1, T+1):
    arr = list(map(int, input().split()))
    arr1, arr2 = [], []

    for i in range(12):
        if i%2:
            arr2.append(arr[i])
        else:
            arr1.append(arr[i])

    ans = 0
    for k in range(3, 7):
        checkArr = arr1[:k]
        if exchange(0, k):
            ans = 1
            break

        checkArr = arr2[:k]
        if exchange(0, k):
            ans = 2
            break

    print(f'#{tc} {ans}')

순서마다 배열을 매번 뽑아서 작성한 코드였다. 사실 급하게 문제를 풀어 제출해야 해서 효율에 대한 깊은 고민을 하지는 못했던 문제가 사실이다.

결과

PASS

모범답안

def babygin(lst):
    if max(lst) >= 3:
        return True
    for k in range(8):
        if lst[k] >= 1 and lst[k + 1] >= 1 and lst[k + 2] >= 1:
            return True
 
 
for tc in range(1, int(input()) + 1):
    cards = list(map(int, input().split()))
    player1 = [0] * 10
    player2 = [0] * 10
    ans = 0
    for i in range(0, len(cards), 2):
        player1[cards[i]] += 1
        player2[cards[i + 1]] += 1
        if babygin(player1):
            ans = 1
            break
        if babygin(player2):
            ans = 2
            break
    print(f'#{tc} {ans}')

어차피 카드의 수는 0부터 9까지이기 때문에 index를 활용해서 카드의 장수를 세는 것이다. 수를 구분할 필요가 없기 때문에 한 인덱스의 값이 3이 되거나, 연달아 3개의 인덱스가 값이 있다면 베이비진이 성립되는 것이다.

효율적인 코드이다.