[백준] 28458 - Mahjong Tenpai (P5)

https://www.acmicpc.net/problem/28458

28458번: Mahjong Tenpai

주어진 마작패가 대기패인지 아닌지 판별하고

대기패라면 완성패가 되기 위해 추가해야 하는 패를 출력하는 문제이다.

 

일단 대기패의 구성 숫자가 13장이고, 완성패의 구성숫자가 14장으로 크지 않고

패의 종류도 많지 않아서 브루트포스를 돌리면 되겠다고 생각했다.

 

그래서 34종류의 모든 패를 하나씩 대기패에 추가해보고

그렇게 구성한 패가 완성패인지 아닌지 판별해서 완성패라면 추가했던 패를 답으로 저장하면 된다.

이를 소스코드로 구현하면 아래와 같다.

 

cards = input().split()
kinds = [
    '1s', '2s', '3s', '4s', '5s', '6s', '7s', '8s', '9s',
    '1t', '2t', '3t', '4t', '5t', '6t', '7t', '8t', '9t',
    '1m', '2m', '3m', '4m', '5m', '6m', '7m', '8m', '9m',
    'e', 's', 'n', 'w', 'h', 'b', 'j'
]
ans = []
for kind in kinds:
    check = cards[:] + [kind]
    check.sort(key=lambda x: (x[1], x[0]) if len(x) > 1 else (x[0],))
    if is츠모():
        ans.append(kind)

if ans:
    print("tenpai")
    print(len(ans))
    print(*sorted(ans))
else:
    print("no tenpai")

 

그러나 이 문제가 까다로웠던 점은 '완성패인지 아닌지 판별' 하는 것이었다.

완성패인지 아닌지 판별하는 방법은 아래와 같다.

 

1. 우선 치또이츠 와 국사무쌍 은 매우 특이한 케이스라서 체크하기가 어렵지 않다.

이것부터 체크해서 치또이츠와 국사무쌍에 해당된다면 완성패로 처리한다.

 

def is츠모():
    for card in set(check):
        if check.count(card) > 4:
            return False

    if is치또이츠():
        return True

    if is국사무쌍():
        return True

    if isGeneral():
        return True

    return False

 

아래는 치또이츠를 판별하는 코드이다.

 

def is치또이츠():
    치또이츠_카운트 = 0
    for card in set(check):
        if check.count(card) == 2:
            치또이츠_카운트 += 1

    if 치또이츠_카운트 == 7:
        return True
    return False

 

아래는 국사무쌍을 판별하는 코드이다.

 

def is국사무쌍():
    max_count = 0
    for card in ['1m', '9m', '1s', '9s', '1t', '9t', 'e', 's', 'n', 'w', 'h', 'b', 'j']:
        if card not in check:
            return False
        max_count = max(max_count, check.count(card))

    if max_count == 1:
        return False
    return True

 

2. 치또이츠도 아니고 국사무쌍도 아니라면 일반적인 완성패 구성을 맞춰야 한다.

즉 머리1개 몸통 4개를 맞춰야 하는데 여기에서도 브루트포스를 이용한다.

구성한 패의 모든 패 종류에 대해 순회하면서 해당 패 종류가 머리가 될 수 있다면

(같은 종류가 2개 이상 있다면) 머리로 처리하고

남은 12장에 대해 몸통을 만들 수 있는지 체크하면 된다.

 

def isGeneral():
    for head in set(check):
        if check.count(head) < 2:
            continue
        temp = check[:]
        temp.remove(head)
        temp.remove(head)
        if canMakeFourBody(temp):
            return True
    return False

 

3. 몸통이 될 수 있는지는 그리디하게 접근하면 된다.

 

def canMakeFourBody(left_card):
    left_card.sort(key=lambda x: (x[1], x[0]) if len(x) > 1 else (x[0],))
    while True:
        if not left_card:
            return True
        for card in left_card:
            if left_card.count(card) >= 3:  # 똑같은 카드가 3장 이상 있다면 일단 몸통으로 바꾸고 봄
                for _ in range(3):
                    left_card.remove(card)
                break
            else:  # 1장 또는 2장이라면 무조건 연속된 3개로 만들어야 함.
                if len(card) == 1:  # 자패가 1장 또는 2장인 경우 몸통을 구성할 수 없다.
                    return False
                num, shape = int(card[0]), card[1]
                # 정렬해서 체크하므로 자기자신보다 숫자가 1, 2 큰 녀석이 존재하는지만 보면 됨.
                if num > 7: # 8 또는 9 가 1 ,2 장 남은거라면 이미 안되는 것.
                    return False
                if left_card.count(f'{num+1}{shape}') > 0 and left_card.count(f'{num+2}{shape}') > 0:
                    left_card.remove(f'{num}{shape}')
                    left_card.remove(f'{num+1}{shape}')
                    left_card.remove(f'{num+2}{shape}')
                    break
                else:
                    return False

 

맨 앞의 패를 체크해서 그 패가 3장 이상이라면 3장을 먼저 몸통으로 처리하고 리스트에서 3장을 제거한다.

 

똑같은 패가 3장 이상이면 그 패는 (자패가 아니라면) 3장으로 몸통이 될 수도 있고, 연속으로 몸통이 될 수도 있지만

3장 미만이라면 오로지 연속으로만 몸통이 될 수 있기 때문에

3장 이상인 경우에는 3장을 묶어서 몸통으로 먼저 체크하는 것이 좋다.

 

3장이상이 안된다면 무조건 연속된 3개 숫자로 봐야하는데,

연속된 3개 숫자를 볼 때는 자기 자신, 자기자신 + 1, 자기자신 + 2 가 존재하는지만 체크하면 된다.

그래서 숫자가 8, 9 인 부분은 체크할 필요가 없다.

숫자 8, 9 가 있었다면 이는 숫자 7을 체크할 때 모두 없어졌어야 한다.

그럼에도 남았다면 절대 연속된 3개로 만들 수 없다.

단, 이렇게 코드를 짜려면 left_card 가 정렬되어 있어야 한다.

 

canMakeFourBody 함수는 매 head 설정마다 호출이 되는데,

check 부터 정렬을 해두었다면 이 함수에서 정렬은 하지 않아도 된다.

하지만 이렇게 작성하는게 더 이해하기 좋은 코드라고 생각한다.

 

최종 정답 코드는 다음과 같다.

 

def canMakeFourBody(left_card):
    left_card.sort(key=lambda x: (x[1], x[0]) if len(x) > 1 else (x[0],))
    while True:
        if not left_card:
            return True
        for card in left_card:
            if left_card.count(card) >= 3:  # 똑같은 카드가 3장 이상 있다면 일단 몸통으로 바꾸고 봄
                for _ in range(3):
                    left_card.remove(card)
                break
            else:  # 1장 또는 2장이라면 무조건 연속된 3개로 만들어야 함.
                if len(card) == 1:  # 자패가 1장 또는 2장인 경우 몸통을 구성할 수 없다.
                    return False
                num, shape = int(card[0]), card[1]
                # 정렬해서 체크하므로 자기자신보다 숫자가 1, 2 큰 녀석이 존재하는지만 보면 됨.
                if num > 7: # 8 또는 9 가 1 ,2 장 남은거라면 이미 안되는 것.
                    return False
                if left_card.count(f'{num+1}{shape}') > 0 and left_card.count(f'{num+2}{shape}') > 0:
                    left_card.remove(f'{num}{shape}')
                    left_card.remove(f'{num+1}{shape}')
                    left_card.remove(f'{num+2}{shape}')
                    break
                else:
                    return False

def isGeneral():
    for head in set(check):
        if check.count(head) < 2:
            continue
        temp = check[:]
        temp.remove(head)
        temp.remove(head)
        if canMakeFourBody(temp):
            return True
    return False

def is치또이츠():
    치또이츠_카운트 = 0
    for card in set(check):
        if check.count(card) == 2:
            치또이츠_카운트 += 1

    if 치또이츠_카운트 == 7:
        return True
    return False

def is국사무쌍():
    max_count = 0
    for card in ['1m', '9m', '1s', '9s', '1t', '9t', 'e', 's', 'n', 'w', 'h', 'b', 'j']:
        if card not in check:
            return False
        max_count = max(max_count, check.count(card))

    if max_count == 1:
        return False
    return True

def is츠모():
    for card in set(check):
        if check.count(card) > 4:
            return False

    if is치또이츠():
        return True

    if is국사무쌍():
        return True

    if isGeneral():
        return True

    return False


cards = input().split()
kinds = [
    '1s', '2s', '3s', '4s', '5s', '6s', '7s', '8s', '9s',
    '1t', '2t', '3t', '4t', '5t', '6t', '7t', '8t', '9t',
    '1m', '2m', '3m', '4m', '5m', '6m', '7m', '8m', '9m',
    'e', 's', 'n', 'w', 'h', 'b', 'j'
]
ans = []
for kind in kinds:
    check = cards[:] + [kind]
    if is츠모():
        ans.append(kind)

if ans:
    print("tenpai")
    print(len(ans))
    print(*sorted(ans))
else:
    print("no tenpai")