[Leet Code] Construct Target Array With Multiple Sums

안녕하세요, 김현지입니다.
5월 2주차 2번째 알고리즘인 Construct Target Array With Multiple Sums의 풀이를 적어보겠습니다.

---

문제

요약
target 배열의 길이와 같은 start 배열은 초기에는 1로만 구성되어있습니다.
이 start 배열의 합으로 배열 안의 요소들을 바꿔가면서 최종적으로 target 을 만들 수 있는지 true, false 를 return 하는 문제입니다.

처음 시도한 방법

문제에서 설명한 방법대로, 무작정 start 배열의 합으로 요소를 바꾸는 방법을 시도했습니다.
문제를 무조건 index 1 부터 시작하는 것으로 잘못 이해했기 때문에 가능했던 알고리즘이 아니였나 싶습니다.
결론적으로는 문제 해결조차 못했습니다.

두번째로 시도한 방법

문제가 start 배열의 합으로 바꾸는 index가 랜덤으로 선택되어야한다는 것을 깨닫고 다시 생각해봤습니다.
그래서 역으로 target을 바꿔가면서 모든 요소가 1이 될 수 있는지를 확인하는 것으로 알고리즘을 변경했습니다.
하지만 역시 Time 에러를 마주했고, 자료구조를 사용해야 한다는 것을 깨달았습니다.

코드 설명

우선 target 배열을 우선순위 큐로 사용했습니다.
큐를 내림차순으로 정렬되도록 초기화한 후에, peek() 한 값이 1이면 반복문을 종료했습니다.

Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
int totalSum = 0;
for (int i: target) {
    totalSum += i;
    queue.add(i);
}

totalSum 은 target 배열의 전체 합입니다.
totalSum 을 기준으로 queue 의 요소들을 조작할 것이기 때문에, 합을 구해주었습니다.
new PriorityQueue<>((a, b) -> b - a); 는 위에서 언급한대로 내림차순으로 정리된 우선순위 큐가 되겠습니다.

while (queue.peek() != 1) {
	// ...
}

while문의 조건은 queue.peek() != 1 입니다.
이것은 queue 가 내림차순으로 정렬되는 우선순위 큐라는 것에서 가능한 조건입니다.

아래에서는 while문 내부 코드를 살펴보겠습니다.

int num = queue.poll();
totalSum -= num;

queue 에서 가장 큰 값을 가져와서 전체 배열의 합에서 빼줍니다.
그러면 이제 totalSum 은 가장 큰 값을 뺀 나머지의 합이 남게 되겠죠.

if (num <= totalSum || totalSum < 1) return false;

만약 가장 큰 값이 나머지의 합보다 크다면, 해당 값은 만들어질 수 없습니다.
또한 totalSum 이 1보다 작다는 것은 나머지 값 중에서 음수 값이 있거나, 유효하지 않은 값이 있는 것입니다.
따라서 해당 조건들은 false 를 return합니다.

num %= totalSum;
totalSum += num;
queue.add(num);

if 문을 통과했다면 유효한 값이므로 num을 나머지의 합인 totalSum 의 나머지를 구해줍니다.
나머지 연산이 아닌 뺄셈을 하면, 연산 수가 늘어나므로 나머지 연산으로 해주었습니다.
그 후에 totalSum 에 바뀐 num 값을 더해주고, queue 에 추가해줍니다.

전체 코드

class Solution {
    public boolean isPossible(int[] target) {
        Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        int totalSum = 0;
        for (int i: target) {
            totalSum += i;
            queue.add(i);
        }

        while (queue.peek() != 1) {
            int num = queue.poll();
            totalSum -= num;

            if (num <= totalSum || totalSum < 1) return false;

            num %= totalSum;
            totalSum += num;
            queue.add(num > 0 ? num: totalSum);
        }

        return true;
    }
}

---

마무리

오늘은 24시간이 끝나지 않고 문제를 해결해서 Solution 보지 않고 알고리즘을 해결하는 것을 성공했습니다!
역시 자료구조를 사용해야 코드가 짧아지고 효율성도 좋아진다는 것을 다시 한 번 느낀 문제였습니다 :)