2023.11.05 Today's Challenge

fabichoi 2023. 11. 5. 23:45

https://leetcode.com/problems/find-the-winner-of-an-array-game/

Find the Winner of an Array Game - LeetCode

Can you solve this real interview question? Find the Winner of an Array Game - Given an integer array arr of distinct integers and an integer k. A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of th

leetcode.com

백퍼 TL 이 날줄 알았지만, 일단 문제가 준 대로 풀어봤다.

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:        
        winner = [0] * (10**6 + 1)
        while True:
            if arr[0] > arr[1]:
                arr = [arr[0]] + arr[2:] + [arr[1]]
                winner[arr[0]] += 1
                if winner[arr[0]] >= k:
                    return arr[0]
            else:
                arr = arr[1:] + [arr[0]]
                winner[arr[1]] += 1
                if winner[arr[1]] >= k:
                    return arr[1]

역시나 TL. 그래서 솔류션을 참고했다. 큐를 써서 풀었다.

솔루션에서는 Streak 이라는 개념을 넣고 풀었다.

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:        
        max_el = max(arr)
        qu = deque(arr[1:])
        cur = arr[0]
        streak = 0

        while qu:
            op = qu.popleft()
            if cur > op:
                qu.append(op)
                streak += 1
            else:
                qu.append(cur)
                cur = op
                streak = 1
            if streak == k or cur == max_el:
                return cur