글 읽기 - 힌트 없을까요?

(追記) (追記ここまで)

힌트 없을까요?

15956번 - 숏코딩

gkfkagkfka12 7년 전 0

어떻게 접근해야 할지 모르겠습니다.

카카오 홈페이지에서 주는 공식 풀이도 이해를 못하겠는데... dfs로 푸는 문제인가요?

접근방법이라도 주시면 감사하겠습니다.

#include <iostream>
#include <string>
#include <cctype> 
#include <map>
#include <set>
using namespace std;
map<string, string> parent;
map<string, string> notEqual;
set<string> ans;
string s;
char type;
string find(string p) {
 if(!p.compare(parent[p])) return p;
 else return parent[p] = find(parent[p]);
}
void uni(string s1, string s2) {
 string s1_root = find(s1);
 string s2_root = find(s2);
 if(s1_root.compare(s2_root)) {
 if(s1.length() < s2.length()) parent[s2_root] = s1;
 else parent[s1_root] = s2;
 }
}
int main(void)
{
 cin >> s;
 int i=0, start=0;
 while(i<s.length()) {
 type=s[i];
 if(type=='=' || type=='!') {
 string temp1 = s.substr(start, i-start);
 if(!parent[temp1].compare("")) {
 parent[temp1] = temp1;
 }
 i+=2; start = i;
 // &를 찾거나 끝까지 감
 while(s[i]!='&') {
 i++;
 if(i>=s.length()) break;
 }
 string temp2 = s.substr(start, i-start);
 if(!parent[temp2].compare("")) {
 parent[temp2] = temp2;
 }
 // 같을 경우에만 같은 집합에 넣는다.
 if(type=='=') {
 // 둘 다 숫자인 경우
 if((temp1[0]=='-' || isdigit(temp1[0])) && (temp2[0]=='-' || isdigit(temp2[0]))){
 int t1 = stoi(temp1), t2 = stoi(temp2);
 // 실제로 같은 값이면 1==1이 제일 짧음
 if(t1==t2) ans.insert("1==1");
 // 실제로 다른 값이면 모순이므로 1==2
 else ans.insert("1==2");
 }
 // 숫자가 아니지만 문자열이 실제로 같으면 1==1
 else if(!temp1.compare(temp2))
 ans.insert("1==1");
 // 위 조건들 모두 실패할 경우 해당 집합에 포함
 else uni(temp1, temp2);
 }
 // 다를 경우 다른 집합으로 분리한다.
 else {
 // 둘 다 숫자인 경우
 if((temp1[0]=='-' || isdigit(temp1[0])) && (temp2[0]=='-' || isdigit(temp2[0]))){
 int t1 = stoi(temp1), t2 = stoi(temp2);
 // 실제로 같은 값이면 1==2
 if(t1==t2) ans.insert("1==2");
 // 실제로 다른 값이면 1==1
 else ans.insert("1==1");
 }
 // 숫자가 아니지만 실제로 같은 값이라면
 else if(!temp1.compare(temp2))
 ans.insert("1==2");
 // 실제로도 다른 경우
 else
 notEqual[find(temp1)]=find(temp2);
 }
 i+=2; start=i;
 }
 else i++;
 }
 for(auto const& cur : parent) {
 if(!notEqual[cur.first].compare("")) {
 string p = find(cur.first);
 if(cur.first.compare(p)) {
 string temp = cur.first;
 temp.append("==").append(p);
 ans.insert(temp);
 }
 }
 else {
 string temp = cur.first;
 temp.append("!=").append(notEqual[find(temp)]);
 ans.insert(temp);
 }
 }
 if(ans.find("1==2")!=ans.end()){
 cout<<"1==2";
 } else {
 int size=0;
 for(auto const& cur : ans) {
 size++;
 cout<<cur;
 if(size<ans.size()) cout<<"&&";
 }
 }
 cout<<'\n';
 return 0;
}

djm03178 7년 전 2

맞은 사람 수에도 나오듯이, 어려운 문제였습니다. 맞은 사람들의 코드 길이를 봐도, 3000바이트 아래의 정답 코드가 거의 없을 정도로 구현도 복잡합니다.

기본적으로는 이런 자료구조를 만들어 내면 됩니다.

"==" 관계인 것들끼리 집합을 만듭니다. 예를 들면 저는 disjoint set을 구현했습니다.
각 집합에는 그 집합을 대표하는 "대장"이 있습니다. "대장"이란 그 집합에서 가장 길이가 짧은 단항식을 말합니다.
하나의 집합에는 둘 이상의 서로 다른 정수가 있으면 안 됩니다. 어떤 집합에 어떤 정수 값이 이미 들어가 있다면, 그 집합에 새로운 정수를 추가하려는 건 무조건 거짓이 됩니다.
"!=" 관계는 두 집합을 연결합니다. 서로 다른 두 집합 사이에는 둘 이상의 "!=" 관계가 있을 수 없습니다. "!=" 관계를 출력할 때는 각 집합의 "대장"들만 출력하면 됩니다.
같은 집합에 속한 단항식끼리 "!=" 관계가 있다면 전체 문장은 거짓입니다.

djm03178 7년 전 1

특별히 어떤 방법으로 풀어야 한다고 정해져있기보다는, 문제에서 정하는 여러 조건들을 잘 정리해서 그에 맞는 자료구조와, 필요한 연산들을 구현해내는 게 중요한 것 같습니다.

gkfkagkfka12 7년 전 0

항상 친절한 답변 너무 감사드립니다. Disjoint set은 상당히 좋은 아이디어네요!

지금 당장 짜볼 수는 없지만 내일 짜보고 어려운 점이 있으면 다시 댓글 남기겠습니다.

감사합니다.

gkfkagkfka12 7년 전 0

@djm03178님 각 문자열을 파싱해서 disjoint set을 만들어보려고 했는데 인덱스 값이 숫자인데 어떤식으로 구현해야 되나요? 아예 string 배열로 빼서 따로 따로 해야되나요 아니면 map을 써야 할까요?

djm03178 7년 전 0

저는 map을 썼습니다.

gkfkagkfka12 7년 전 0

저도 map을 써서 구현했습니다. 근데 예제에서 int==float가 float==int가 되도 상관없는거 맞나요?

djm03178 7년 전 0

둘이 같은 식이고 길이도 같으니 상관 없죠.

gkfkagkfka12 7년 전 0

제 허졉한 코드에서 뭐가 문젠지 알려주실수있나요 ᅲᅲ 노력은 해봤는데 계속 틀리네여...

#include <iostream>
#include <string>
#include <cctype> 
#include <map>
#include <set>
using namespace std;
map<string, string> parent;
map<string, string> notEqual;
set<string> ans;
string s;
char type;
string find(string p) {
 if(!p.compare(parent[p])) return p;
 else return parent[p] = find(parent[p]);
}
void uni(string s1, string s2) {
 string s1_root = find(s1);
 string s2_root = find(s2);
 if(s1_root.compare(s2_root)) {
 if(s1.length() < s2.length()) parent[s2_root] = s1;
 else parent[s1_root] = s2;
 }
}
int main(void)
{
 cin >> s;
 int i=0, start=0;
 while(i<s.length()) {
 type=s[i];
 if(type=='=' || type=='!') {
 string temp1 = s.substr(start, i-start);
 if(!parent[temp1].compare("")) {
 parent[temp1] = temp1;
 }
 i+=2; start = i;
 // &를 찾거나 끝까지 감
 while(s[i]!='&') {
 i++;
 if(i>=s.length()) break;
 }
 string temp2 = s.substr(start, i-start);
 if(!parent[temp2].compare("")) {
 parent[temp2] = temp2;
 }
 // 같을 경우에만 같은 집합에 넣는다.
 if(type=='=') {
 // 둘 다 숫자인 경우
 if((temp1[0]=='-' || isdigit(temp1[0])) && (temp2[0]=='-' || isdigit(temp2[0]))){
 int t1 = stoi(temp1), t2 = stoi(temp2);
 // 실제로 같은 값이면 1==1이 제일 짧음
 if(t1==t2) ans.insert("1==1");
 // 실제로 다른 값이면 모순이므로 1==2
 else ans.insert("1==2");
 }
 // 숫자가 아니지만 문자열이 실제로 같으면 1==1
 else if(!temp1.compare(temp2))
 ans.insert("1==1");
 // 위 조건들 모두 실패할 경우 해당 집합에 포함
 else uni(temp1, temp2);
 }
 // 다를 경우 다른 집합으로 분리한다.
 else {
 // 다를 경우인데 실제로는 같은 값이라면 1==1
 if(!temp1.compare(temp2))
 ans.insert("1==1");
 // 실제로도 다른 경우
 else
 notEqual[find(temp1)]=find(temp2);
 }
 i+=2; start=i;
 }
 else i++;
 }
 for(auto const& cur : parent) {
 if(!notEqual[cur.first].compare("")) {
 string p = find(cur.first);
 if(cur.first.compare(p)) {
 string temp = cur.first;
 temp.append("==").append(p);
 ans.insert(temp);
 }
 }
 else {
 string temp = cur.first;
 temp.append("!=").append(notEqual[temp]);
 ans.insert(temp);
 }
 }
 int size=0;
 for(auto const& cur : ans) {
 size++;
 cout<<cur;
 if(size<ans.size()) cout<<"&&";
 }
 cout<<'\n';
 return 0;
}