0. 문제

정수 배열 nums가 주어지며, 이 배열은 2 * n 개의 정수로 이루어져 있습니다.

다음 조건을 만족하도록 nums를 n 개의 쌍(pair)으로 나누어야 합니다.

각 원소는 정확히 한 쌍에 속해야 합니다.
각 쌍의 두 원소는 같은 값이어야 합니다.
nums를 위 조건에 맞게 나눌 수 있으면 true, 그렇지 않으면 false를 반환하세요.

예제 1

• 입력: nums = [3,2,3,2,2,2]

• 출력: true

• 설명:
  배열에 총 6개의 원소가 있으므로, n = 6 / 2 = 3개의 쌍을 만들어야 합니다.
  다음과 같이 쌍을 구성할 수 있습니다.

  (2, 2)
  (3, 3)
  (2, 2)

  모든 쌍이 같은 원소로 구성되므로 true 반환.
  

예제 2

• 입력: nums = [1,2,3,4]
• 출력: false
• 설명:
  배열에 총 4개의 원소가 있으므로, n = 4 / 2 = 2개의 쌍을 만들어야 합니다.
  하지만 같은 숫자로 이루어진 쌍을 만들 방법이 없으므로 false 반환.

제약조건

nums.length == 2 * n
1 <= n <= 500
1 <= nums[i] <= 500

1. 나의 풀이

• 시간복잡도: $O(N)$
• numDistribution[i]는 nums 배열 내의 정수 i의 개수를 의미.
• numDistribution[i]의 개수를 확인하면서 홀수이면 pair 생성이 불가능하니까 false 리턴. 짝수이면 만들 수 있는 pair의 개수를 currentPair에 누적합.
• currentPair와 goalPair를 비교해 결과 리턴.

class Solution {
    public boolean divideArray(int[] nums) {
        int[] numDistribution = new int[501];
        int goalPair = nums.length / 2;
        int currentPair = 0;

        for (int num: nums)
            numDistribution[num]++;

        for (int numOfElement: numDistribution) {
            if (numOfElement % 2 != 0)
                return false;
            currentPair += numOfElement / 2;
        }
        if (currentPair == goalPair)
            return true;
        return false;
    }
}

2. 최적화

• 시간복잡도: $O(N)$
• 애초에 2 * n개의 정수로 구성된 배열에서 모든 수가 pair로 구성되면 n개의 pair일 수 밖에 없다. (어떤 바보가 생각없이 코드짜냐)
• currentPair 관련 부분은 삭제해도 무관하다.

class Solution {
    public boolean divideArray(int[] nums) {
        int[] freq = new int[501];

        for(int i = 0; i<nums.length; i++){
            freq[nums[i]]++;
        }

        for(int i = 0; i<501; i++){
            if(freq[i]%2 != 0){
                return false;
            }
        }

        return true;
    }
}