990. Satisfiability of Equality Equations

Satisfiability of Equality Equations

문제 내용

a==b 또는 b!=c 등의 동일 확인 기호가 주어졌을 경우 해당 수식이 모두 성립하면 true 하나라도 성립하지 않으면 false를 return 해라.

 

접근 방법

문제를 생각해 보자.

["a==b","b!=a"]

a는 b와 같지만 b는 a와 같지 않다. 답은 당연히 false가 된다. 

그 이유는 위의 두 식이 성립 하지 않기 때문이다.

["a==b","b==a"]

성립하기 위해서는 위와 같이 정의 되어야 한다.

그럼 조금더 길게 봐보자.

["a==b","b==c","a==c"]

이것은 성립하는가?

그렇다 a,b,c는 모두 동일하다고 볼 수 있다.

만약에

["a==b","b!=c","a==c"]

이경우는 어떠한가? 성립하지 않는다. b와 c도 같아야 하기 때문이다.

이것을 그림으로 나타내면 아래와 같다.

분명히 b와 c는 Group A라는 동일 그룹에 속하는데, 같지 않다라고 표현한것이다.

이것을 몇개의 그룹으로 생각해 보자.

이 문제는 성립하는가?

["a==b","b==c","d==e"]

그렇다 완벽히 성립한다.

그런다면

["a==b","b==c","d==e", "c!=e"]

c와 e는 같지 않은가? 같지 않아도 문제가 없기 때문에 false는 아니다.

만약에 ["a==b","b==c","d==e", "c!=e" , "a==d"]

일경우는 문제가 된다.

왜냐하면 a와 d가 같은 그룹에 있다는 의미이기 때문이다.

그런데 c와 e는 한 그룹에 있으면 안된다.

여기서 문제의 접근을 착안 할 수 있다. 주어진 문제가 몇개의 Group으로 이루어지는지 우선 추측한다.

그리고 같지 않다고 말하는 공식이 성립하는지 여부를 확인하면 된다.

어떤 객체가 동일 그룹인지 여부를 가장 쉽게 판별할 수 있는 알고리즘은 Union-find 이다.

2020.09.14 - [Problem Solving] - Union find

이것을 이용해서 문제를 풀어 보자.

1. 동일한 값들이 뭉쳐있는 그룹을 만들자.
2. 같지 않다를 갖고 있는 객체의 그룹이 진짜로 동일하지 않은지 확인하자.
   1. 만약 두개의 객체가 동일 그룹을 갖고 있다면 false 이다

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function(equations) {
    let arr = new Array(26).fill(null);
    
    for(const equation of equations){
        if(equation.charAt(1) === '='){
            const left = equation.charCodeAt(0) - 'a'.charCodeAt(0);
            const right = equation.charCodeAt(3) - 'a'.charCodeAt(0);
            union(left, right);
        }       
    }
   
    for(const equation of equations){
        if(equation.charAt(1) === '!'){
            const left = equation.charCodeAt(0) - 'a'.charCodeAt(0);
            const right = equation.charCodeAt(3) - 'a'.charCodeAt(0);

            if(find(left) === find(right)) return false;
        }       
    }

    return true;
    
    function union(a, b){
        const left = find(a);
        const right = find(b);
        if(left > right){
            arr[right] = left;
        } else if(left < right){
            arr[left] = right;
        }
    }
    
    function find(idx){
        if(arr[idx]){
            return arr[idx] = find(arr[idx]);
        } else {
            return idx;
        }
    }
    
};

시간 복잡도는 O(N) 이다.

위 코드에서 신경써야 할 것은 union 부분이다. 순환 참조를 피하기 위해서 가장 좌측값이 항상 top이든, 가장 우측값이 top이든 둘중에 하나를 꼭 선택해서 Parent를 만들어야 한다.