[BOJ] 12886. 돌 그룹 (JavaScript)

BOJ 12886. 돌그룹

스터디 그룹 덕분에 오랜만에 BOJ에서 문제를 풀어보게 됐다

3의 배수일 때만 성공할 수 있다는 조건을 생각해내는 것도 어려웠고,
콜스택 한도 초과, 시간 초과 때문에 더더욱 힘들었다

회고

성공/실패조건

• 세 수의 합이 3의 배수일 때만 성공 가능, 아니면 무조건 실패
  • x < y < z 일 때, x + y + z = (x + x) + (y - x) + z이므로 세 수의 합은 항상 동일함
  • x = y = z, x + y + z = n일 때, 3 * x = n 이므로 세 수의 합은 3의 배수
  • 이거 생각을 못해서..

재귀

• 초반에 문제를 잘못 풀었던 것도 있고
• 함수 호출 비용 때문에 시간도 오래 걸린 듯

Array <=> Queue

• C++/Java/Python에는 Queue나 Heap이 내장되어 있지만, JS는 직접 코딩해야 하는 문제가 있다
• 여기서는 구현의 편의를 위해 Array의 shift()를 그냥 썼는데, LinkedList나 Queue 등 좀더 빠른 자료구조를 구현해서 활용했다면 시간 복잡도가 좀더 줄지 않았을까?

다른 블로그 도움 없이도 잘 풀 수 있도록 노오력을 좀 더 하자..!

• 참고 블로그: https://whereisusb.tistory.com/234

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

/**
 * @param {number[]} start 입력 값
 * @returns {boolean} 같은 수가 될 수 있는지 아닌지
 */
const findResult = (start) => {
  const [a, b, c] = start.sort((a, b) => a - b);
  
  // 실패 조건
  if ((a + b + c) % 3 !== 0) return false;

  const visited = new Set([]);
  visited.add(start.join(""));
  const queue = [start];
  
  // 처음에 재귀로 풀었지만, 스택 한도 초과 때문에 while 적용
  while (queue.length) {
    const [x, y, z] = queue.shift();

    // 성공 조건
    if (x === y && y === z) return true;

    // 돌 두 개 선택
    // visited 계산 미리해서 아예 큐에 넣지 않아야 시간초과 안남
    if (x < y) {
      const next = [x + x, y - x, z].sort((a, b) => a - b);
      const nextStr = next.join("");
      if (!visited.has(nextStr)) {
        visited.add(nextStr);
        queue.push(next);
      };
    };
    
    if (y < z) {
      const next = [x, y + y, z - y].sort((a, b) => a - b);
      const nextStr = next.join("");
      if (!visited.has(nextStr)) {
        visited.add(nextStr);
        queue.push(next);
      };
    };
    
    if (x < z) {
      const next = [x + x, y, z - x].sort((a, b) => a - b);
      const nextStr = next.join("");
      if (!visited.has(nextStr)) {
        visited.add(nextStr);
        queue.push(next);
      };
    };
  };
  return false;
}

/**
 * solution
 * 
 * @param {string} str 입력, 돌 세 개 "a b c"
 * @returns {number} 같은 개수로 만들수 있으면 1, 아니면 0
 */
const solution = (str) => {
  const start = str.split(" ").map(Number);
  return findResult(start) ? 1 : 0;
};

let q = "";
rl.on("line", (str) => {
  q = str;
  rl.close();
}).on("close", (str) => {
  console.log(solution(q));
  process.exit();
});