소프트웨어에 대한 모든 것

LeetCode 풀기 - 1688. Count of Matches in Tournament 본문

알고리즘/LeetCode

LeetCode 풀기 - 1688. Count of Matches in Tournament

앤테바 2021. 11. 8. 08:29
반응형

1688. Count of Matches in Tournament

https://leetcode.com/problems/count-of-matches-in-tournament/

 

Count of Matches in Tournament - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

문제)

솔루션1)

문제안에 정답이 있다.

 

짝수 - n/2 matches, n/2 teams advance

홀수 - (n-1) / 2 matches, (n-1)/2 + 1 teams advance

class Solution:
    def numberOfMatches(self, n: int) -> int:        
        matches = []
        while n > 1:
            if n & 1 == 0:
                # even
                matches.append(n//2)
                n = n//2
            else:
                # odd
                matches.append((n-1)//2)
                n = (n-1)//2 + 1
        return sum(matches)

솔루션2)

한 번 게임(match)을 진행하면 한 팀이 제거된다.

최종 승자 한 팀이 남을 때 까지 게임을 진행해야 한다.

10팀이 있으면 9번 게임이 진행되면 한 팀(최종승자)가 남게된다.

즉, n개의 팀이 있으면 n-1 게임이 진행되면 최종 승자 한 팀이 남게된다.

class Solution:
    def numberOfMatches(self, n: int) -> int:     
        return n-1

 

 

반응형
Comments