변수들 간의 관계를 나타내는 등식 배열이 주어졌다고 가정해 봅시다. 각 문자열 equations[i]는 길이가 4이며, "a==b" 또는 "a!=b" 두 가지 형태 중 하나입니다. 여기서 a와 b는 한 글자짜리 변수 이름을 나타내는 소문자입니다. 이 문제의 목표는 주어진 모든 등식을 동시에 만족하도록 변수에 정수를 할당할 수 있을 때만 true를 반환하는 것입니다.
예를 들어 입력이 ["a==b","b==c","a==c"]라면, 세 변수 a, b, c를 모두 같은 값으로 할당할 수 있으므로 결과는 true입니다.
문제 해결 접근법
이 문제는 유니온-파인드(Union-Find), 즉 서로소 집합 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
'==' 연산으로 연결된 변수들은 하나의 그룹으로 묶습니다.
'!=' 연산이 주어진 두 변수가 이미 같은 그룹에 속해 있다면 모순이 발생하므로 false를 반환합니다.
구체적인 풀이 단계는 다음과 같습니다.
getParent() 메서드를 정의합니다. 이 메서드는 문자 x와 맵 m을 인자로 받으며 다음과 같이 동작합니다.
m[x] == x이면 x를 그대로 반환합니다.
그렇지 않으면 m[x] := getParent(m[x], m)으로 갱신한 후 m[x]를 반환합니다. 이 과정에서 경로 압축(path compression)이 일어나 이후 탐색 속도가 빨라집니다.
메인 메서드에서는 다음 작업을 수행합니다.
equal과 notEqual 두 개의 배열을 정의하고, parent라는 이름의 맵을 생성합니다.
n := e의 크기로 설정합니다.
i를 0부터 n-1까지 반복합니다.
parent[e[i][0]] := e[i][0], parent[e[i][3]] := e[i][3]으로 초기화합니다.
e[i][1]이 '='이면 i를 equal 배열에, 그렇지 않으면 notEqual 배열에 삽입합니다.
i를 0부터 equal 배열의 크기-1까지 반복합니다.
index := equal[i]로 설정하고, u와 v를 각각 e[index][0], e[index][3]으로 지정합니다.
parent[getParent(u, parent)] := parent[getParent(v, parent)]를 통해 두 변수가 속한 집합을 하나로 합칩니다.
i를 0부터 notEqual 배열의 크기-1까지 반복합니다.
index := notEqual[i]로 설정하고, u와 v를 각각 e[index][0], e[index][3]으로 지정합니다.
getParent(u, parent) == getParent(v, parent)라면 false를 반환합니다.
모든 검사를 통과하면 true를 반환합니다.
여기서 중요한 포인트는 '==' 등식을 먼저 모두 처리한 뒤 '!=' 부등식을 검사한다는 것입니다. 이 순서를 지켜야 같음 관계가 완전히 병합된 상태에서 충돌 여부를 정확하게 확인할 수 있습니다.
시간 복잡도는 경로 압축이 적용된 유니온-파인드 덕분에 사실상 선형에 가까운 O(N·α(N))이며, 알파벳은 26개뿐이므로 공간 복잡도 역시 상수 공간으로 처리됩니다.
다음 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
char getParent(char x, map <char, char> m){
if(m[x] == x) return x;
return m[x] = getParent(m[x], m);
}
bool equationsPossible(vector<string>& e) {
vector <int> equal;
vector <int> notEqual;
map <char, char> parent;
int n = e.size();
for(int i = 0; i < n; i++){
parent[e[i][0]]= e[i][0];
parent[e[i][3]]= e[i][3];
if(e[i][1] == '='){
equal.push_back(i);
}else{
notEqual.push_back(i);
}
}
for(int i = 0; i < equal.size(); i++){
int idx = equal[i];
char u = e[idx][0];
char v = e[idx][3];
parent[getParent(u, parent)] = parent[getParent(v, parent)];
}
for(int i = 0; i < notEqual.size(); i++){
int idx = notEqual[i];
char u = e[idx][0];
char v = e[idx][3];
if(getParent(u, parent) == getParent(v, parent)) return false;
}
return true;
}
};
main(){
vector<string> v1 = {"a==b","b==c","a==c"};
Solution ob;
cout << (ob.equationsPossible(v1));
}입력
["a==b","b==c","a==c"]
출력
true