문제 정의
배열 arr을 첫 번째이자 유일한 인수로 받는 자바스크립트 함수를 작성해야 합니다.
배열 arr은 다음 두 가지 형태 중 하나의 문자열 등식으로 구성됩니다.
'X === Y'
'X !== Y'
여기서 X와 Y는 임의의 변수입니다.
함수의 목표는 배열에 포함된 모든 등식에 적절한 숫자를 할당했을 때, 모든 등식이 참(true)이 되도록 만들 수 있는지 판별하는 것입니다.
예를 들어, 함수에 다음과 같은 입력이 주어진다고 가정해 보겠습니다.
const arr = ['X===Y', 'Y!==Z', 'X===Z'];
그렇다면 출력 결과는 다음과 같아야 합니다.
const output = false;
출력 결과 해설
X, Y, Z에 어떤 값을 선택하더라도 세 개의 등식을 모두 동시에 만족시킬 수는 없습니다. 'X===Y'와 'Y!==Z'가 성립하려면 X와 Z는 서로 달라야 하는데, 'X===Z'는 이와 모순되기 때문입니다.
풀이 접근 방법
이 문제는 유니온 파인드(Union-Find) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
먼저 모든 '===' 등식을 처리하여 같은 값을 가져야 하는 변수들을 하나의 집합으로 묶습니다.
이후 '!==' 등식을 검사하여 두 변수가 서로 다른 집합에 속하는지 확인합니다. 만약 같은 집합에 속한다면 해당 조건은 만족될 수 없습니다.
find 함수는 경로 압축(path compression) 기법을 사용해 탐색 속도를 높이고, add 함수는 랭크 기반 병합(rank-based union)을 통해 두 집합을 효율적으로 합칩니다.
예제 코드
이 문제를 해결하기 위한 전체 코드는 다음과 같습니다.
const arr = ['X===Y', 'Y!==Z', 'X===Z'];
const validateEquations = (arr = []) => {
const map = {};
const len = {};
const inValids = [];
const find = (item) => {
while(map[item] && item !== map[item]){
map[item] = map[map[item]];
item = map[item];
};
return item;
};
const add = (a, b) => {
const first = find(a);
const second = find(b);
if(first === second){
return;
};
if(len[first] < len[second]){
map[first] = second;
len[second] += len[first];
}else{
map[second] = first;
len[first] += len[second];
}
}
arr.forEach((item) => {
const X = item[0];
const Y = item[4];
map[X] = map[X] || X;
map[Y] = map[Y] || Y;
len[X] = len[X] || 1;
len[Y] = len[Y] || 1;
if(item[1] === '!'){
inValids.push([X, Y]);
}else{
add(X, Y);
};
});
return inValids.every(([a, b]) => find(a) !== find(b))
};
console.log(validateEquations(arr));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
false