백준 15956 숏코딩 (c++)

(으아아)

 

 

예외처리에 매우 매우 매우 주의해가며 푼다

 

string s; //원본 문자열
vector<string> tokens; //&&단위로 끊은 조건식들
map<string, string> parent; //==로 연결되어있는것들 부모배열
vector < pair<string, string>> diff; //!=로 연결된것들

map<string, vector<string>> group; //==집단들
map<string, bool> digit; //상수가 포함된 집단

이렇게 사용하여 풀었다

 

string find_parent(string s)
{
	if (parent[s] == s) return s;
	else return parent[s] = find_parent(parent[s]);
}

void union_find(string s1, string s2)
{
	s1 = find_parent(s1);
	s2 = find_parent(s2);

	parent[s1] = s2;
}

유니온 파인드(분리 집합)을 위한 함수

 

bool is_digit(string s)
{
	return (atoi(s.c_str()) != 0 || s.compare("0") == 0);
}

상수 문자열을 판별하는 함수

 

bool compare(string a, string b)
{
	return a.size() < b.size();
}

문자열을 길이순으로 정렬하기 위해 사용한 비교식

 

ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
cin >> s;
string tmp;
for (int i = 0;i<s.size();i++)
{
	if (s[i] == '&')
	{
		tokens.push_back(tmp);
		tmp.clear();
		i++;
	}
	else
	{
		tmp += s[i];
	}
}
if (tmp != "")
{
	tokens.push_back(tmp);
	tmp.clear();
}

먼저 &&단위로 쪼개서 저장

 

for (auto token : tokens)
{
	bool op = false;
	string str[2];
	str[0] = "";
	str[1] = "";
	int stridx = 0;
	if (token.find('=') == string::npos)
	{
		if (parent.find(token) == parent.end())
		{
			parent[token] = token;
		}
		continue;
	}
	for (int i = 0; i < token.size(); i++)
	{
		if (token[i] == '!')
		{
			stridx = 1;
			i++;
		}
		else if (token[i] == '=')
		{
			op = true;
			stridx = 1;
			i++;
		}
		else
		{
			str[stridx] += token[i];
		}
	}
	
	if (parent.find(str[0]) == parent.end())
	{
		parent[str[0]] = str[0];
	}
	if (parent.find(str[1]) == parent.end())
	{
		parent[str[1]] = str[1];
	}
	if (op == false)
	{
		diff.push_back({ str[0],str[1] });
		continue;
	}
	if (op == true)
	{
		union_find(str[0], str[1]);
	}

}

각각의 조건식들을 !=와 ==로 나누어

!=는 따로 저장해두고

==는 유니언 파인드 하여 집단으로 만들어준다

 

for (auto a : parent)
{
	string str = find_parent(a.first);
	group[str].push_back(a.first);
}

부모찾기를 한번 더 돌려주면 모든 노드가 자기자신(루트일 경우)혹은 최종 부모를 가리키게 된다

부모를 키로하여 모든 자식을 순회할 수 있도록 group map에 저장해준다

 

string ans = "";
for (auto& a : group)
{
	sort(a.second.begin(), a.second.end(), compare);
	string d = "";
	for (auto t : a.second)
	{
		if (is_digit(t))
		{
			digit[a.first] = true;
			if (d == "")
			{
				d = t;
			}
			else
			{
				cout << "1==0" << endl;
				return 0;
			}
		}
	}
	if (a.second.size() < 2) continue;
	string tmp = a.second[0];
	for (int i = 1; i < a.second.size(); i++)
	{
		ans += a.second[i] + "==" + tmp + "&&";
	}
}

먼저 group에 저장된 자식 노드들을 문자열의 길이 오름차순으로 정렬한다.

 

각각의 자식을 확인하며 상수 노드인지 체크한다

 

한 그룹에서 상수 노드가 두개 이상이면 전체가 무조건 false가 되므로 가장 짧은 false 조건식 아무거나 출력하고 끝낸다

(유니언 파인드할 때, 값이 같은 상수는 걸러졌다)

 

또한 상수가 들어간 집단은 나중에 필요하므로 체크해둔다

 

문자열 하나로 이루어진 비교식은 성립하지 않으므로 패스

 

각 그룹의 맨 앞은 가장 짧은 문자열이므로 그 문자열을 돌려쓰며 == 집단을 ans에 적어준다

 

set<pair<string, string>> diffset;
for (int i = 0; i < diff.size(); i++)
{
	string a = find_parent(diff[i].first);
	string b = find_parent(diff[i].second);
	if (a == b)
	{
		cout << "1==0" << endl;
		return 0;
	}
	if (a < b) swap(a, b);
	if (digit[a] == true && digit[b] == true) continue;
	diffset.insert({ a,b });
}

!= 집단을 작성해줘야한다.

만약 양변의 부모를 확인했을때 같은 집단이면 무조건 false를 반환하는 조건식을 출력 후 종료

 

중복을 거르기 위해 크기순으로 set에 넣어준다

상수가 들어있는 그룹끼리는 무조건 같지 않으므로 굳이 써 줄 필요 없으니 패스

 

for (set<pair<string,string>>::iterator i = diffset.begin(); i != diffset.end(); i++)
{
	string a = (*i).first;
	string b = (*i).second;
	ans += group[a][0] + "!=" + group[b][0] + "&&";
}

그렇게 생긴 set을 순회하며 ans에 출력

 

if (ans.empty())
{
	cout << "1==1" << endl;
	return 0;
}

혹시 모든 조건이 무조건 참인 식일경우 ans에 아무것도 들어있지 않게 될 수 있다

그럴땐 항상 참인 가장 짧은 조건식 아무거나 하나 출력후 종료

ans.pop_back();
ans.pop_back();
cout << ans << endl;
return 0;

불필요한 &&를 뺀 후 정답 출력

 

 

전체코드

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <climits>
#include <sstream>
#define ll long long
using namespace std;
#define INF 1e9

string s; //원본 문자열
vector<string> tokens; //&&단위로 끊은 조건식들
map<string, string> parent; //==로 연결되어있는것들 부모배열
vector < pair<string, string>> diff; //!=로 연결된것들

map<string, vector<string>> group; //==집단들
map<string, bool> digit; //상수가 포함된 집단

bool is_digit(string s)
{
	return (atoi(s.c_str()) != 0 || s.compare("0") == 0);
}

bool compare(string a, string b)
{
	return a.size() < b.size();
}

string find_parent(string s)
{
	if (parent[s] == s) return s;
	else return parent[s] = find_parent(parent[s]);
}

void union_find(string s1, string s2)
{
	s1 = find_parent(s1);
	s2 = find_parent(s2);

	parent[s1] = s2;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> s;
	string tmp;
	for (int i = 0;i<s.size();i++)
	{
		if (s[i] == '&')
		{
			tokens.push_back(tmp);
			tmp.clear();
			i++;
		}
		else
		{
			tmp += s[i];
		}
	}
	if (tmp != "")
	{
		tokens.push_back(tmp);
		tmp.clear();
	}
	/*if (tokens.size() == 1)
	{
		cout << tokens[0] << endl;
		return 0;
	}*/
	for (auto token : tokens)
	{
		bool op = false;
		string str[2];
		str[0] = "";
		str[1] = "";
		int stridx = 0;
		if (token.find('=') == string::npos)
		{
			if (parent.find(token) == parent.end())
			{
				parent[token] = token;
			}
			continue;
		}
		for (int i = 0; i < token.size(); i++)
		{
			if (token[i] == '!')
			{
				stridx = 1;
				i++;
			}
			else if (token[i] == '=')
			{
				op = true;
				stridx = 1;
				i++;
			}
			else
			{
				str[stridx] += token[i];
			}
		}
		
		if (parent.find(str[0]) == parent.end())
		{
			parent[str[0]] = str[0];
		}
		if (parent.find(str[1]) == parent.end())
		{
			parent[str[1]] = str[1];
		}
		if (op == false)
		{
			diff.push_back({ str[0],str[1] });
			continue;
		}
		if (op == true)
		{
			union_find(str[0], str[1]);
		}

	}
	for (auto a : parent)
	{
		string str = find_parent(a.first);
		group[str].push_back(a.first);
	}

	string ans = "";
	for (auto& a : group)
	{
		sort(a.second.begin(), a.second.end(), compare);
		string d = "";
		for (auto t : a.second)
		{
			if (is_digit(t))
			{
				digit[a.first] = true;
				if (d == "")
				{
					d = t;
				}
				else
				{
					cout << "1==0" << endl;
					return 0;
				}
			}
		}
		if (a.second.size() < 2) continue;
		string tmp = a.second[0];
		for (int i = 1; i < a.second.size(); i++)
		{
			ans += a.second[i] + "==" + tmp + "&&";
		}
	}

	set<pair<string, string>> diffset;
	for (int i = 0; i < diff.size(); i++)
	{
		string a = find_parent(diff[i].first);
		string b = find_parent(diff[i].second);
		if (a == b)
		{
			cout << "1==0" << endl;
			return 0;
		}
		if (a < b) swap(a, b);
		if (digit[a] == true && digit[b] == true) continue;
		diffset.insert({ a,b });
	}

	
	for (set<pair<string,string>>::iterator i = diffset.begin(); i != diffset.end(); i++)
	{
		string a = (*i).first;
		string b = (*i).second;
		ans += group[a][0] + "!=" + group[b][0] + "&&";
	}
	
	if (ans.empty())
	{
		cout << "1==1" << endl;
		return 0;
	}
	ans.pop_back();
	ans.pop_back();
	cout << ans << endl;
	return 0;


}

 

생각보다 너무 어려운 문제라 애먹었다

이것저것 예외가 많고 예외를 떠올리기도 어려워서 반례가 없었다면 풀지 못했을 것 같다