[LeetCode] 954. Array of Doubled Pairs

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

Array of Doubled Pairs - LeetCode

Array of Doubled Pairs.

 

-10만 부터 10만까지의 수로 된 배열이 주어졌을 때,

이 배열을 재 정렬하여 2*i + 1 < arr.size()인 모든 i에 대해

arr[2*i + 1] = 2*arr[2*i] 

를 만족할 수 있는지의 문제다.

 

간단히 말하면 arr이 어떤 수가 다른 수의 두 배가 되는 쌍으로만 이루어진 배열인가를 묻고 있다.

악필 풀이는 아래와 같다.

 

 

먼저, plus배열과 minus 배열을 만들어 준다.

따로 만드는 이유는, plus는 2배를 하면 커지고, minus는 2배를 하면 작아지기 때문이다.

2배를 하면 둘다 커지도록 만들기 위해 minus에는 절대값으로 저장해준다.

 

이제 arr을 훑으며 각각의 배열 index의 해당 index가 나온 수를 저장해준다.

int plus[100005], minus[100005];
    for (int i=0; i<=100000; i++) {
        plus[i] = 0;
        minus[i] = 0;
    }
    for (auto k:arr) {
        if (k>=0) plus[k]++;
        else minus[-k]++;
    }

 

이제 plus와 minus 모두 앞에서부터 훑어주면 오름차순으로 정렬된 것이나 마찬가지다.

이제 i=0 부터 50000까지 훑어주며 plus, minus 배열을 A라 할 때,

A[i] > 0 이면 A[2*i] 도 0보다 커야한다.

A[i] > 0 인데 A[2*i] 가 0이면 조건에 안맞으므로 바로 false를 던져주자.

(while 말고 바로 A[2*i] 를 A[i] 만큼 깎고 음수가 되면 false를 던져도 된다.

배열 수가 충분히 적어 while로도 충분하다.

50000까지 훑는 이유는 50001부터는 2배인 수가 없기 때문에 필요가 없다.

 

for (int i=0; i<=50000; i++) {
    while (plus[i]>0) {
        if (plus[2*i]>0) {
        plus[i]--;
        plus[2*i]--;
        } else return false;
    }
    while (minus[i]>0) {
        if (minus[2*i]>0) {
        minus[i]--;
        minus[2*i]--;
        } else return false;
    }
}

 

마지막으로 0부터 100000까지 훑어주며 남아있는 수가 있다면 이는 쌍이 없는 경우이므로 false를 던지고,

끝까지 진행되었다면 true를 던져주자.

훑지 않고 sum으로 관리하는 방법도 있다.

 

for (int i=0; i<=100000; i++) {
    if (plus[i]>0) return false;
    if (minus[i]>0) return false;
    }
return true;

 

 

전체 코드는 아래와 같다.

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        int plus[100005], minus[100005];
        for (int i=0; i<=100000; i++) {
            plus[i] = 0;
            minus[i] = 0;
        }
        for (auto k:arr) {
            if (k>=0) plus[k]++;
            else minus[-k]++;
        }
        for (int i=0; i<=50000; i++) {
            while (plus[i]>0) {
                if (plus[2*i]>0) {
                    plus[i]--;
                    plus[2*i]--;
                } else return false;
            }
            while (minus[i]>0) {
                if (minus[2*i]>0) {
                    minus[i]--;
                    minus[2*i]--;
                } else return false;
            }
        }
        for (int i=0; i<=100000; i++) {
            if (plus[i]>0) return false;
            if (minus[i]>0) return false;
        }
        return true;
    }
};