LeetCode 2020-11-05: Min. Cost to Move Chips to The Same Pos

LeetCode の daily problem に挑戦した記録です。

今日の問題は Minimum Cost to Move Chips to The Same Position (easy)。

問題の概要

• チップが置かれている場所を列挙した配列が与えられるので、チップをすべて同じ場所に「最小のコスト」で移動させたときのコストを求める
• チップの移動にかかるコストは以下の通り
  • 一つ隣 (右/左) に移動する場合のコストは 1
  • 二つ先の隣に移動する場合のコストはなし

考え方

• ちゃんと考えれば easy 相当の問題であることが理解できますね
  • 二つ先に移動させる操作が コストなし であることをうまく利用しよう
• 例えば以下のケースを考えてみよう
  • 
  • このように配置されたチップを、コストをかけない操作だけを使って左側に寄せてみると以下のようになる
  • 
  • この状態から、最小のコストで 同じ位置 にチップを移動させるには、チップの量が少ない山のすべてのチップをもう一方のチップの山に移動 させれば OK
  • 概念的にはこんな感じだけど、実際に配列などを使ってチップ移動をシミュレートしようとするのは空間計算量的に効率が悪くて 🙅‍♀️ ですね
• では実際にはどうするか？
  • チップの置かれている位置に着目しよう
  • 実は上記の図で色分けしているように、位置を表す数値が偶数であるチップと奇数であるチップとでそれぞれチップの山を作れば OK
    • 偶数同士、もしくは奇数同士の位置におけるチップの移動はコストがかからないのでね
  • そういうわけで、この問題は単に 位置が偶数のチップの数と、位置が奇数のチップの数をそれぞれ数え上げ、そのうちの小さい方を解とする という問題に解釈し直すことができるわけですね
• ここまでくれば、あとは愚直に実装すれば 100% beats 達成できますね 🤗

コード

class Solution {
    public int minCostToMoveChips(int[] position) {
        int oddCount = 0;
        int evenCount = 0;
        for (int p : position) {
            if ((p & 1) == 1) {
                oddCount++;
            } else {
                evenCount++;
            }
        }

        return Math.min(oddCount, evenCount);
    }
}