[LeetCode] 954. Array of Doubled Pairs

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

Array of Doubled Pairs - LeetCode

---

문제

짝수 길이의 정수 배열 arr 이 주어지면, 모든 0 <= i < len(arr) / 2 인 i 에 대해서 arr[2 * i + 1] = 2 * arr[2 * i] 의 형태로 재정렬할 수 있다면 true 를 반환하고, 그렇지 않다면 false 를 반환하라.

 

예제

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

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].

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

---

풀이

재정렬된 배열의 조건을 나열하면 다음과 같다.

 

arr[1] = 2 * arr[0]

arr[3] = 2 * arr[2]

arr[5] = 2 * arr[4]

arr[7] = 2 * arr[6]

...

 

배열(arr)에서 가장 작은 값은 위와 같이 표현했을 때, 등호의 오른쪽에 있을까 아니면 왼쪽에 있을까?

 

배열에서 가장 작은 값의 경우, 자신보다 작은 값이 배열 내에 없기 때문에 등호의 왼쪽에 존재할 수가 없다. 즉, 오른쪽에 위치하여 본인보다 2배 큰 값과 매칭 될 것이다. 그렇다면, 두 번째로 작은 값은 어떠할까? 이미 가장 작은 값이 매칭 되었기 때문에 두 번째로 작은 값 역시 자신의 2배 큰 값과 바로 매칭 시킬 수 있을 것이다.

 

이처럼 가장 작은 값부터 시작하여 탐욕적(Greedy)인 방식으로 문제를 접근해 볼 수 있다.

 

우선 배열 내 각 값이 몇 번 등장하는지 카운트한다. 이 카운트 값은, 이후 과정에서 어떤 값이 이미 다른 값과 매칭이 되어있는지 여부를 체크하기 위함이다.

const numCounter = {};

arr.forEach(num => {
    if (!numCounter[num]) {
        numCounter[num] = 0;
    }
    numCounter[num] += 1;
});

Greedy하게 접근하기 위해서 주어진 arr을 오름차순으로 정렬할 차례이다. 이때 한 가지 생각해볼 것은 arr 안에 존재하는 중복된 값을 고려해야 하는가 이다.

 

결론은 중복된 값은 하나로 처리하는 것이 효율적이다. 예를 들어 arr = [2, 1, 1, 2] 인 경우를 생각해보자.

arr = [2, 1, 1, 2]

1. 중복을 허용할 경우
  sortedArr = [1, 1, 2, 2]
  - 중복 숫자의 구분을 위해 다음과 같이 표시: sortedArr = [1(1), 1(2), 2(1), 2(2)]
  - 정렬된 배열을 순차적으로 돌면서 숫자들을 매칭해 나감
      1) 1(1) => 2(1) 매칭
      2) 1(2) => 2(2) 매칭
  - 총 2번의 매칭 과정이 수행

2. 중복 값을 없앤 경우
  sortdArr = [1, 2]
  - 정렬된 배열을 순차적으로 돌면서 숫자들을 매칭해 나감
      1) 1 => 2 매칭
  - 총 1번의 매칭 과정이 수행

이러한 예시처럼 중복 값을 처리하면 반복 횟수를 줄여 실행 시간을 조금이라도 단축시킬 수 있다.

 

숫자들을 매칭해 나가기 전에 마지막으로 한 가지 케이스만 더 고려해보자. Greedy하게 접근하기 위해서 위 예시처럼 정렬시킨 배열을 사용할 수 있는데, 배열에 음수가 포함되어 있는 경우를 생각해야 한다.

 

만약 arr = [-2, -4] 라고 하면, 이 arr을 정렬하면 [-4, -2]가 된다. 문제는 이때 맨 앞의 원소를 선택하여 x2를 하게 되면 -8이 된다는 것이다. 양수와 달리 음수는 절댓값의 결과가 작을수록 실제 값이 크기 때문이다. 이를 고려해서 만약 값이 음수라면 x2가 아니라 /2를 취하여 매칭 시키도록 해야 한다.

 

위 내용과 더불어 몇 가지 종료 조건을 추가하면 다음과 같은 코드를 통해서 탐욕적(Greedy)하게 숫자들을 매칭 시킬 수 있다.

let answer = true;

const sortednum = new Set(arr.sort((a, b) => a - b));
for (let num of sortednum) {
    if (!numCounter[num]) { continue; }

    const isMinus = num < 0;
    if (isMinus && num % 2) { 
        answer = false; 
        break; 
    }

    let next = isMinus ? num / 2 : num * 2;
    if (!numCounter[next]) { 
        answer = false; 
        break; 
    }
	
    numCounter[num] = 0;
    numCounter[next] -= numCounter[num];
    if (numCounter[next] < 0) { 
        answer = false; 
        break; 
    }
}

 

 

Github: 954.js

GitHub - opwe37/Algorithm-Study