[문제풀이] 두 큐 합 같게 만들기

const solution = (n, wires) => {
  const graph = {};

  wires.forEach(([n1, n2]) => {
    graph[n1] ? graph[n1].push(n2) : (graph[n1] = [n2]);
    graph[n2] ? graph[n2].push(n1) : (graph[n2] = [n1]);
  });

  let min = n;
  for (let i = 1; i <= n; i++) {
    const visited = Array.from({ length: n + 1 }, () => false);
    const parent = Array.from({ length: n + 1 }, (_, i) => i);

    findParent(graph, visited, parent, i);

    for (let j = 1; j <= n; j++) {
      if (i === j) continue;
      const child = findChild(parent, j, i);
      min = Math.min(min, Math.abs(child + 1 - (n - (child + 1))));
    }
  }

  return min;
};

const findParent = (graph, visited, parent, node) => {
  visited[node] = true;
  for (let n of graph[node]) {
    if (visited[n]) continue;
    parent[n] = node;
    findParent(graph, visited, parent, n);
  }
};

const findChild = (tree, node, root) => {
  const treeArr = Object.entries(tree);
  if (node === root) return treeArr.length - 1;

  let count = 0;

  const find = (n) => {
    const child = treeArr.filter(([k, v]) => v === n);

    if (child.length <= 0) return;
    if (n === root) return;

    child.forEach(([k, v]) => {
      count++;
      find(Number(k));
    });
  };
  find(node);
  return count;
};

import kotlin.math.*

fun 전력망_둘로_나누기(n: Int, wires: Array<IntArray>): Int {
    val graph = mutableMapOf<Int, MutableList<Int>>()
### 구하고자 하는 것은 무엇인가?

- 두 큐의 원소의 합이 같아지게 만들때 필요한 작업의 최소 횟수를 구해야 합니다.

### 1. 이해

- pop, insert 묶음이 하나의 작업 단위입니다.
- 처음에 길이가 같은 두 큐가 주어집니다.
- 큐1과 큐1의 원소의 최대값은 10^9입니다.
- 두 큐의 원소 합을 같게 만들 수 없는 경우 -1을 리턴합니다.

### 2.계획

- 모든 큐의 원소들의 합을 구하고 2로 나누어 절반 값을 구합니다.
- 큐가 2로 나누어 떨어지지 않는다면 -1을 리턴합니다.
- 큐1, 큐2 둘 중 하나에라도 절반 값보다 큰 값을 포함하면 -1을 리턴합니다.
- 두 큐의 합이 같아질 때까지 과정을 반복합니다.
    - 큐의 합이 큰쪽에서 작으로쪽으로 원소를 이동시키면서 작업의 횟수를 1씩 증가시킵니다.
    - 각 큐의 상태가 원래 상태로 돌아오면 -1을 리턴합니다.(?)

### 3. 실행

```jsx
const solution = (queue1, queue2) => {
  const total = sum(queue1) + sum(queue2);

  if (total % 2 !== 0) return -1;

  const half = Number(total / 2);

  if (queue1.some((e) => e > half) || queue2.some((e) => e > half)) return -1;

  let count = 0;
  let sum1 = sum(queue1);
  let sum2 = sum(queue2);

  const merge = [...queue1, ...queue2, ...queue1, ...queue2];
  let s1 = 0,
    s2 = queue1.length;

  while (sum1 !== half) {
    if (s2 > merge.length) return -1;

    if (sum1 > sum2) {
      const p1 = merge[s1];

      sum1 -= p1;
      sum2 += p1;

      s1++;
    } else {
      const p2 = merge[s2];

      sum1 += p2;
      sum2 -= p2;

      s2++;
    }

    count++;
  }

  return count;
};

const sum = (arr) => {
  return arr.reduce((acc, cur) => acc + cur, 0);
};

fun 두_큐_합_같게_만들기(queue1: IntArray, queue2: IntArray): Int {
    val total:Long = sum(queue1) + sum(queue2)
    val half : Long = total /2

    if (total % 2 != 0.toLong()) return -1;
    if(queue1.any { it >half } || queue2.any { it > half }) return -1

    var count = 0
    var sum1:Long = sum(queue1)
    var sum2:Long = sum(queue2)

    val merge = queue1 + queue2 + queue1 + queue2
    var s1 = 0
    var s2 = queue1.size

    while (sum1 != half){
        if(s2 > merge.size || s1 > merge.size) return -1

        if(sum1 > sum2){
            val p = merge[s1].toLong()

            sum1 -= p
            sum2 += p
            s1++
        }else{
            val p = merge[s2].toLong()

            sum1 += p
            sum2 -= p
            s2++
        }
        count ++
    }
    return count
}

fun sum(arr : IntArray) : Long = arr.fold(0.toLong()) { acc, cur -> acc + cur }