[Leetcode][954] Array of Doubled Pairs

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

---

 

map을 하나 만든다.

map의 key는 A 배열의 요소 값이 되고 value는 해당 값이 나온 횟수가 된다.

A배열은 절대값 기준으로 오름차순 정렬한다.

문제를 보면 A[i]를 2배 한 값이 있는지만 체크하면 된다.

A[i]를 1/2 한 값을 찾거나 *2 한 값을 찾아야 하기 때문에 절대값 오름차순 정렬을 함으로서 *2 한 값만 있는지 체크하기 위함이다.

ex) A = {-4, 1, -2} 인 경우 정렬하지 않으면 1/2 (-2)도 체크하고 *2 (-8)한 값도 체크해야 한다. 절대값 기준 오름차순 정렬한다면 A = {1, -2, -4}가 될 것이기 때문에 *2한 값만 체크해도 된다.

값을 찾을 때 더 빠르게 찾기 위해 map을 이용했다. 해당 값을 찾았으면 value값을 갱신한다.(사용한 개수를 빼준다.)

만약 값을 찾을 수 없는 경우 false를 반환한다.

배열을 탐색하면서 현재 값의 *2한 값을 찾아야하

만약 A[i]값이 0이라면 곱하기한 값도 0이므로 이 때는 예외처리 해준다.

 

시간복잡도는 O(NlogN).

 

 

---

 

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/954.%20Array%20of%20Doubled%20Pairs.cpp

 

---

 

https://leetcode.com/problems/array-of-doubled-pairs/discuss/203183/JavaC%2B%2BPython-Match-from-the-Smallest-or-Biggest-100

위 링크 풀이방법 되게 좋은 듯.