ゼロから始めるLeetCode Day110「1535. Find the Winner of an Array Game」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day109「213. House Robber II」

次回
ゼロから始めるLeetCode Day111「682.Baseball Game」

Twitterやってます。

問題

1535. Find the Winner of an Array Game
難易度はMedium。
久しぶりに問題集以外から解きました。

問題としては、整数の入った配列arr と，整数kが与えられている。

配列の最初の2つの要素（すなわち arr[0]とarr[1]）の間でゲームが行われます。ゲームの各ラウンドでは， arr[0] とarr[1]を比較し、大きい方の整数が勝ち、0 の位置にとどまり、小さい方の整数は配列の末尾に移動します。ゲームは、ある整数がk回のラウンドに連続して勝利したときに終了します。
ゲームに勝つ整数を返します。
なお、ゲームの勝者が存在することが保証されています。

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let’s see the rounds of the game:
Round | arr | winner | win_count
1 | [2,1,3,5,4,6,7] | 2 | 1
2 | [2,3,5,4,6,7,1] | 3 | 1
3 | [3,5,4,6,7,1,2] | 5 | 1
4 | [5,4,6,7,1,2,3] | 5 | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

解法

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        dic = collections.defaultdict(int)
        for i in range(1,len(arr)):
            if arr[i] < arr[i-1]:
                arr[i],arr[i-1] = arr[i-1],arr[i]
            dic[arr[i]] += 1
            if dic[arr[i]] >= k:
                return arr[i]
        return arr[-1]
# Runtime: 760 ms, faster than  62.35%  of  Python3  online submissions for  Find the Winner of an Array Game.

# Memory Usage: 27.7 MB, less than  24.52%  of  Python3  online submissions for  Find the Winner of an Array Game.

単純にarr[i]とarr[i-1]の比較を行い、大きければ要素の入れ替えを行います。

例えば、arr = [2,1,3,5,4,6,7]に

for i in range(1,len(arr))
arr[i-1]
arr[i]

この形を当てはめると

arr[i-1](2) > arr[i](1)

となり、arr[i-1]の値である2をarr[i-1]の値である1と入れ替える。

これでdic[arr[i]]を加算することで、何回比較した際に大きな数値であったかを辞書に値と回数をセットで記憶させます。
具体的には以下のように、

defaultdict(<class 'int'>, {2: 1})  
defaultdict(<class 'int'>, {2: 1, 3: 1})  
defaultdict(<class 'int'>, {2: 1, 3: 1, 5: 1})  
defaultdict(<class 'int'>, {2: 1, 3: 1, 5: 2})

ご存知の通り、辞書は{key,value}のセットで要素を管理します。
keyで要素の対象である値を、valueでその要素が登場した回数をプラスをしていき、その後に指定された回数であるk回と同値以上になった時点でarrのi番目を返してあげる、という形です。

なお、末尾のarr[-1]というのは必ず勝者が存在するという文が存在しているため、仮にfor文が何もなく終わってしまった場合は配列の末尾の要素が必ず勝者であるためです。

単純な問題だったのでMediumっぽくは無かったですね。しかし、これより速く、そしてメモリの容量も削減できる解答があるかもしれないので何かあったらコメントいただけると幸いです。

では今回はここまで。
お疲れ様でした。