[LeetCode] 2856. Minimum Array Length After Pair Removals (C++)

문제

 

https://leetcode.com/problems/minimum-array-length-after-pair-removals/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

 

풀이

 

난이도: Medium 

 

 

 

어떤 식으로 쌍을 맞춰줘야 될지 이리저리 해봤지만, 결국에는 간단한 그리디 방식으로 해결된다.

 

 

 

아래 배열에서 쌍을 맞춰보자.

1 1 1 1 2 2 2 5 5 5

 

작은 값부터 쌍을 맞춰 버리면, 5가 두 개 남아버린다.

1 1 1 1 2 2 2 5 5 5

 

그렇다고 큰 값부터 먼저 쌍을 맞추면, 1이 4개나 남아버린다.

1 1 1 1 2 2 2 5 5 5

 

정답은 아래처럼 적절한 쌍을 맞춰 줘야한다.

[1, 5] , [1, 5] , [2, 5] , [1, 2] ,[1, 2]

 

도대체 쌍을 맞추는 방법에 규칙이 있을까?

 

 

 

 

사실 특정 값이 절반 이상이 아닌 이상,

어떻게든 모두 쌍을 맞춰 줄 수 있다.

 

값들의 개수가 큰 순서대로 정렬해서  a, b, c, d,.... 개 라고 해보자.

모든 수들은 서로 다르기 때문에 항상 한쪽이 큰 쌍을 이룰 수 있다.

가장 많 수인 a에서 하나와 그다음 많은 b에서 하나를 쌍을 이뤄서 빼내고, 다시 a, b, c, d... 를 만들어 이를 반복한다.

 

1 1 1 1 2 2 2 5 5 5

1 1 1 5 5 5 2 2

1 1 5 5 2 2

2 2 1 5 

2 5

 

 

 

그러면 결국에 전체가 짝수개라면, 모든 쌍의 완성이 되고

전체가 홀수개라면, 한 개가 남게 된다.

 

 

하지만, 특정 수가 절반 이상이라면, 이 수로 모든 다른 수와 쌍을 이뤄도 나머지가 남게 된다.

따라서 이 예외 케이스만 코드로 구현하면 된다.

 

 

 

코드