[leetcode #954] Array of Doubled Pairs

Problem

Given an array of integers arr of even length, return true if and only if it is possible to reorder it such that arr[2 * i + 1] = 2 arr[2 i] for every 0 <= i < len(arr) / 2.

Example 1:

Input: arr = [3,1,3,6]
Output: false

Example 2:

Input: arr = [2,1,2,6]
Output: false

Example 3:

Input: arr = [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: arr = [1,2,4,16,8,4]
Output: false

Constraints:

・ 0 <= arr.length <= 3 * 10⁴
・ arr.length is even.
・ -10⁵ <= arr[i] <= 10⁵

Idea

얼핏 보면 문제는 쉬워보인다. 주어진 array를 정렬 후 탐색하면서 2배가 되는 값이 있는지 없는지 확인한 후, 없으면 false를 리턴하고 2배가 되는 값이 있으면 array에서 빼버리면 된다. 하지만 array에서 값을 빼는 건 쉽지 않으므로 대부분은 map에 array에 있는 값들을 저장하려고 할 것이다.

우선 array에 있는 값들을 map의 key로, 해당 값의 빈도수를 value로 정한다. array를 전부 탐색하고 나면 (value)=(frequency)인 map이 만들어진다. 처음엔 정렬한 array를 탐색하면서 2배에 해당하는 값이 없으면 false를 리턴하고 있는 경우 빈도수를 1씩 감소시키는 방법으로 알고리즘을 짰다. 하지만 Test Case를 만들어 몇 번 돌려보니 틀린 결과가 나오는 case가 발생했다.

원인은 음수와 0이었다. 음수의 경우 단순히 정렬을 하면 되는 것이 아니라 더 큰 값이 앞으로 오도록 해야 한다. 음수의 경우 2배를 했을 경우 더 작은 값이 되어버리기 때문이다. 그래서 정렬을 할 때 단순히 값을 비교하는 것이 아니라 절대값을 기준으로 정렬을 해야 한다.

0의 경우는 2배를 했을 때도 0이 나오기 때문에 조심해야 한다. 나는 array를 탐색하다 0이 나왔을 경우 count가 1일 때 false를 리턴하도록 하여 해결했지만 빈도수를 계산하여 음수가 나오게 유도한 후 다음 iteration 때 false를 리턴하는 방법도 있다.

map에서 지원하는 getOrDefault를 활용하면 내가 짠 코드보다 훨씬 짧고 효율적으로 짤 수 있을 것이다. map을 다룰 때마다 getOrDefault가 생각이 잘 안 나는 이유는 무엇일까. 역시 자주 써서 뇌리에 남아야 금방 떠오르는 법인데 주어진 것만 쓰다보니 잘 생각이 나지 않나보다.

알고리즘을 정리하면 다음과 같다.

1. array를 절대값으로 정렬한다. (primitive type은 comparator를 넣지 못하므로 Integer Array로 바꿔준다.)
2. array를 탐색하면서 key가 array의 element, value를 해당 element의 빈도수인 map을 만든다.
3. array를 탐색하면서 Doubled Pair가 있는지 확인한다.
   a. array의 element가 map에 없을 경우 doubled pair로 판명되어 제외되었으므로 다음 iteration으로 넘어간다.
   b. array element의 2배에 해당하는 값의 빈도수가 0보다 작을 경우 false를 리턴한다.
   c. array element와 그 2배에 해당하는 값의 빈도수를 각각 1씩 낮춘다.
4. loop를 다 돌았을 경우 true를 리턴한다.

Solution

class Solution {
    public boolean canReorderDoubled(int[] arr) {
    	Integer[] intArray = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(intArray, new CustomComparator());
        Map<Integer, Integer> map = new ConcurrentHashMap<>();

    	for (Integer k : intArray) {
            if (!map.containsKey(k))
            	map.put(k, 1);
            else
            	map.put(k, map.get(k) + 1);
    	}

    	for (Integer i : intArray) {
            if (!map.containsKey(i))
            	continue;
            int doubled = i * 2;

            if (!map.containsKey(doubled))
            	return false;

            if (map.get(i) == 1) {
            	if (i == 0)
                    return false;
            	map.remove(i);
            } else
            	map.put(i, map.get(i)-1);           

            if (map.get(doubled) == 1)
            	map.remove(doubled); 
            else
            	map.put(doubled, map.get(doubled) - 1);
        }

    	return true;
    }
}

class CustomComparator implements Comparator<Integer> {
    @Override public int compare(Integer i1, Integer i2) {
	if (i1 < 0 && i2 > 0)
	    return -1;
        else if (i1 < 0 && i2 < 0)
            return i1.compareTo(i2) * -1;
        else
            return i1.compareTo(i2);
    }
}

leetcode 결과는 최악이니 다른 좋은 방법이 있는지 찾아봐야겠다.

Reference

https://leetcode.com/problems/array-of-doubled-pairs/