[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 등 좀더 빠른 자료구조를 구현해서 활용했다면 시간 복잡도가 좀더 줄지 않았을까?
다른 블로그 도움 없이도 잘 풀 수 있도록 노오력을 좀 더 하자..!
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();
});
Author And Source
이 문제에 관하여([BOJ] 12886. 돌 그룹 (JavaScript)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@johnwi/BOJ-12886.-돌-그룹-JavaScript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)