1217. Play with Chips

출처: leetcode.com/problems/play-with-chips/

분류: Greedy, Easy

---

접근방식

문제 자체를 이해하기가 어려웠던 문제였습니다. 

간단히 요약하면, 

chips 에는 chip이 있는 index 가 적혀있습니다. 

즉, chips = [2,2,2,3,3] 이렇게 주어져 있다면, 아래와 같은 모습으로 생각할 수 있습니다.

칩이 있는 인덱스	1	2	3
칩의 개수	0	3	2

이 칩들은 좌우로 2칸을 움직일 때는 비용이 없고 1칸을 움직일 때는 1의 비용이 듭니다.

여기서 이 칩을 한 곳으로 모으는 방법은 2가지 방법이 있습니다.

2에 있는 칩3개를 3으로 옮기는 방법 --> 비용 2
3에 있는 칩 2개를 2로 옮기는 방법 --> 비용 3

당연히 3을 2로 옮기는게 좋겠죠??

다음으로 제한사항을 보면 칩의 개수는 1 ~ 100개밖에 안되지만 인덱스는 1 <= chips[i] <= 10^9 의 범위를 가지고 있죠.
인덱스가 굉장히 크지만 잘 생각해보면 인덱스는 짝수인지 홀수인지 정도의 의미만 가질 뿐 수의 크기 자체는 중요하지 않다는 것을 알 수 있습니다.  

해결방법

어차피 짝수 인덱스에 있는 칩들은 비용없이 한 곳으로 모을 수가 있습니다. 홀수도 마찬가지죠.

결국 짝수 인덱스에 있는 칩과 홀수 인덱스에 있는 칩의 수를 계산해서 더 적은 쪽을 옮겨주는게 최소비용이 됩니다. :)

chips를 돌면서 짝수, 홀수의 개수를 체크해준 다음 더 적은 쪽을 리턴해주면 되겠죠?

func minCostToMoveChips(_ chips: [Int]) -> Int {
  var even = 0
  var odd = 0

  for chipPosition in chips {
    if chipPosition % 2 == 0 {
    	even += 1
    } else {
    	odd += 1
    }
  }

  return even >= odd ? odd : even
}

 

배운점

풀이 자체는 간단했지만 문제자체를 이해하기가 쉽지 않았던 문제였습니다.