글 읽기 - 힌트 없을까요?

gkfkagkfka12 5년 전 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 5년 전 2

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

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

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

djm03178 5년 전 1

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

gkfkagkfka12 5년 전 0

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

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

감사합니다.

gkfkagkfka12 5년 전 0

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

djm03178 5년 전 0

저는 map을 썼습니다.

gkfkagkfka12 5년 전 0

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

djm03178 5년 전 0

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

gkfkagkfka12 5년 전 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;
}

djm03178 5년 전 0

1==2&&a==a

는 무조건 거짓이므로 1==0 등을 출력해야 합니다.

gkfkagkfka12 5년 전 0

수정했는데 그래도 틀리네요 ...ㅠ 게시글 수정했습니다.

ehfkswl 5년 전 0

djm03178님 가능하시면 위에 제코드도 봐주시면 감사하겠습니다

djm03178 5년 전 0

위가 어디인가요

ehfkswl 5년 전 0

15956번 문제에 대하여 따로 모아놓은 질문 글 중 이글 다음에 있는 것입니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

힌트 없을까요?

gkfkagkfka12 5년 전 0

djm03178 5년 전 2

djm03178 5년 전 1

gkfkagkfka12 5년 전 0

gkfkagkfka12 5년 전 0

djm03178 5년 전 0

gkfkagkfka12 5년 전 0

djm03178 5년 전 0

gkfkagkfka12 5년 전 0

djm03178 5년 전 0

gkfkagkfka12 5년 전 0

ehfkswl 5년 전 0

djm03178 5년 전 0

ehfkswl 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말