파이썬으로 이진 문자열 점수에서 배구 경기 승자 판별하기

문제 이해하기

배구 경기의 득점 기록을 이진 문자열로 표현했다고 가정해 보겠습니다. 이때 다음 조건에 따라 경기의 최종 승자를 판별해야 합니다.

기본 규칙: 두 팀이 서로 대결하며, 먼저 15점(n)에 도달한 팀이 승리합니다. 단, 양 팀 모두 14점에 도달한 경우는 예외입니다.
듀스 규칙: 양 팀이 모두 14점에 도달한 상황에서는 이후 2점 차이를 먼저 만들어내는 팀이 승자가 됩니다.

주어진 이진 문자열에서 '0'은 우리 팀이 실점한 것(즉, 상대 팀의 득점), '1'은 우리 팀이 득점한 것을 의미합니다. 문자열을 끝까지 읽으며 우리 팀이 최종적으로 승리했는지("Team won") 아니면 패배했는지("Team lost")를 판단하는 것이 목표입니다.

예를 들어 입력이 score = "1001100110111001110011011", n = 15라면 출력은 "Team won"이 됩니다.

풀이 접근 방법

이 문제는 점수 카운터 배열과 두 단계의 반복문으로 해결할 수 있습니다. 전체 알고리즘은 다음과 같습니다.

득점 카운터 score_cnt = [0, 0]를 초기화합니다. 인덱스 0은 상대 팀의 점수(실점), 인덱스 1은 우리 팀의 점수(득점)를 저장합니다.
첫 번째 단계(일반 라운드): 문자열을 순회하면서 각 문자를 정수로 변환해 해당 인덱스의 점수를 1씩 증가시킵니다.
- 상대 팀이 먼저 n점에 도달하고 우리 팀 점수가 n-1 미만이면 → "Team lost"
- 우리 팀이 먼저 n점에 도달하고 상대 팀 점수가 n-1 미만이면 → "Team won"
- 양 팀 모두 n-1점(14점)에 도달하면 듀스 상황이므로 카운터를 0으로 초기화하고 첫 번째 루프를 종료합니다.
두 번째 단계(듀스 라운드): 남은 문자열을 계속 순회하며 두 팀 점수 차이가 정확히 2가 되는 순간을 찾습니다.
- 상대 팀 점수가 더 크면 → "Team lost"
- 우리 팀 점수가 더 크면 → "Team won"

파이썬 구현 예제

아래 코드를 통해 더 쉽게 이해할 수 있습니다.

def predictWinner(score, n):
    score_cnt = [0, 0]
    for i in range(len(score)):
        pos = ord(score[i]) - ord('0')
        score_cnt[pos] += 1
        if (score_cnt[0] == n and score_cnt[1] < n - 1):
            return "Team lost"
        if (score_cnt[1] == n and score_cnt[0] < n - 1):
            return "Team won"
        if (score_cnt[0] == n - 1 and
            score_cnt[1] == n - 1):
            score_cnt[0] = 0
            score_cnt[1] = 0
            break
    i += 1
    for i in range(i, len(score)):
        pos = ord(score[i]) - ord('0')
        score_cnt[pos] += 1
        if (abs(score_cnt[0] - score_cnt[1]) == 2):
            if (score_cnt[0] > score_cnt[1]):
                return "Team lost"
            else:
                return "Team won"

score = "1001010101111011101111"
n = 15
print(predictWinner(score, n))

입력

"1001010101111011101111"

출력

Team won

동작 원리 살펴보기

위 예제의 문자열에는 '1'이 총 15번 등장하며, 15번째 '1'이 나타난 시점의 '0' 등장 횟수는 14회 미만입니다. 따라서 일반 라운드 조건인 score_cnt[1] == n and score_cnt[0] < n - 1이 충족되어 듀스 규칙까지 갈 필요 없이 우리 팀의 승리를 의미하는 "Team won"이 바로 반환됩니다.

마무리 정리

이 알고리즘의 시간 복잡도는 O(m)입니다(m은 문자열의 길이). 문자열을 한 번만 순회하면서 조건을 검사하므로 매우 효율적이며, 공간 복잡도 역시 크기 2짜리 고정 배열만 사용하므로 O(1)입니다. 배구처럼 듀스 규칙이 적용되는 스포츠 경기의 승패를 시뮬레이션할 때 활용할 수 있는 대표적인 패턴이니, 직접 다양한 입력값을 넣어 동작을 확인해 보시기 바랍니다.