파이썬으로 미니언 게임 승자의 이름과 점수 구하기

문제 개요

두 명의 플레이어 아말(Amal)과 비말(Bimal)이 게임을 하고 있습니다. 게임 규칙은 다음과 같습니다.

• 두 플레이어는 동일한 문자열 s를 가지고 시작합니다.
• 각자 문자열 s의 글자들을 사용해 부분 문자열(substring)을 만들어야 합니다.
• 비말은 반드시 자음으로 시작하는 단어를 만들어야 합니다.
• 아말은 반드시 모음으로 시작하는 단어를 만들어야 합니다.
• 게임은 두 플레이어가 만들 수 있는 모든 부분 문자열을 완성하면 종료됩니다.

점수 계산 방식은 다음과 같습니다. 플레이어가 만든 부분 문자열이 원래 문자열 s 안에서 등장하는 횟수만큼 1점씩 획득합니다. 우리는 이 게임의 승자와 그 점수를 구해야 합니다.

예를 들어 입력이 s = "BANANA"라면 출력은 Bimal, 12가 됩니다. 그 이유는 아래 표와 같습니다.

해결 접근 방식

모든 부분 문자열을 일일이 생성하면 비효율적입니다. 핵심 아이디어는 인덱스 i에서 시작할 수 있는 부분 문자열의 개수는 정확히 len(word) − i개라는 점입니다. 따라서 각 위치의 문자가 모음인지 자음인지만 판별해 해당 플레이어에게 점수를 누적하면 됩니다. 이 방법은 시간 복잡도 O(n)으로 매우 효율적입니다.

• vowels := 모음 집합 {'A', 'E', 'I', 'O', 'U'}
• p1 := 0 (비말의 점수)
• p2 := 0 (아말의 점수)
• 문자열의 각 인덱스 i와 문자 c에 대해 반복:
  • c가 모음이면: p2 := p2 + (문자열 길이 − i)
  • 그렇지 않으면: p1 := p1 + (문자열 길이 − i)
• p1 > p2이면 ('Bimal', p1) 반환
• p2 > p1이면 ('Amal', p2) 반환
• 같으면 'Draw' 반환

구현 예제

다음 파이썬 코드로 위 로직을 쉽게 이해할 수 있습니다.

def solve(word):
    vowels = set('AEIOU')
    p1 = 0
    p2 = 0
    for i, c in enumerate(word):
        if c in vowels:
            p2 += len(word) - i
        else:
            p1 += len(word) - i
    if p1 > p2:
        return 'Bimal', p1
    elif p2 > p1:
        return 'Amal', p2
    else:
        return 'Draw'

word = "BANANA"
print(solve(word))

입력

"BANANA"

출력

('Bimal', 12)