백준_15956_숏코딩(해결 못함)

https://www.acmicpc.net/problem/15956

15956번: 숏코딩

해결 한 부분

> ==으로 묶여있는 set과 !=으로 묶여있는 set를 구분지었다.

> a==a, a!=a

 

해결 못 한 이유

>식이 false라면 false , true이면 true인 식을 출력해야하는데 그 부분을 간과하였다.

> union - find가 int로 돌아가서 복잡하다(input은 string).

 

코드

import sys, copy

from collections import defaultdict

 

input = sys.stdin.readline

 

class DisjointSet:

    def __init__(self, n):

        self.data = [-1 for _ in range(n)]

        self.size = n

 

    def upward(self, change_list, index):

        value = self.data[index]

        if value < 0:

            return index

        

        change_list.append(index)

        return self.upward(change_list, value)

 

    def find(self, index):

        change_list = []

        result = self.upward(change_list, index)

 

        for i in change_list:

            self.data[i] = result

        return result

 

    def union(self,x ,y):

        x = self.find(x)

        y = self.find(y)

 

        if x == y:

            return

        

        if self.data[x] < self.data[y]:

            self.data[y] = x

        elif self.data[x] > self.data[y]:

            self.data[x] = y

        else:

            self.data[x] -= 1

            self.data[y] = x

        

        self.size -= 1

 

if __name__ == "__main__":

    S = input().strip('\n') #strip() ---> 엔터제거

 

    logic_list = S.split('&&')

 

    if len(logic_list) == 1 and '==' in logic_list[0]:

        tmp = logic_list[0].split('==')

        if tmp[0] == tmp[1]:

            print("1==1")

            sys.exit()

    

    if len(logic_list) == 1 and '!=' in logic_list[0]:

        tmp = logic_list[0].split('!=')

        if tmp[0] == tmp[1]:

            print("1!=1")

            sys.exit()

 

    monomial_same = defaultdict(set)

    monomial_diff = defaultdict(set)

 

    def isInt(word):

        try:

            word = int(word)

            return word

        except ValueError:

            return word

 

    for i in logic_list:

        if '==' in i:

            tmp_same = i.split('==')

            tmp_same[0] = isInt(tmp_same[0])

            tmp_same[1] = isInt(tmp_same[1])

            monomial_same[tmp_same[0]].add(tmp_same[1])

        else:

            tmp_diff = i.split('!=')

            tmp_diff[0] = isInt(tmp_diff[0])

            tmp_diff[1] = isInt(tmp_diff[1])

            monomial_diff[tmp_diff[0]].add(tmp_diff[1])

    monomial_same_list = list(monomial_same.items())

    monomial_diff_list = list(monomial_diff.items())

    

    #one-hot encoding

    one_hot_encoding = defaultdict(int)

    

    same_count = 0

    #case ==

    for group in monomial_same_list:

        if group[0] not in one_hot_encoding:

            one_hot_encoding[same_count] = group[0]

            one_hot_encoding[group[0]] = same_count

            monomial_same[same_count] = monomial_same[group[0]]

            del monomial_same[group[0]]

            same_count += 1

        for element in group[1]:

            if element not in one_hot_encoding:

                one_hot_encoding[same_count] = element

                one_hot_encoding[element] = same_count

                if element in monomial_same:

                    monomial_same[same_count] = monomial_same[element]

                    del monomial_same[element]

                same_count += 1

 

    #case !=

    diff_count = same_count

    for group in monomial_diff_list:

        if group[0] not in one_hot_encoding:

            one_hot_encoding[group[0]] = diff_count

            one_hot_encoding[diff_count] = group[0]

            monomial_diff[diff_count] = monomial_diff[group[0]]

            del monomial_diff[group[0]]

            diff_count += 1

        for element in group[1]:

            if element not in one_hot_encoding:

                one_hot_encoding[element] = diff_count

                one_hot_encoding[diff_count] = element

                if element in monomial_diff:

                    monomial_diff[diff_count] = monomial_diff[element]

                    del monomial_diff[element]

                diff_count += 1

 

    print(monomial_same)

    print(monomial_diff)

    #make disjoint set each case(same, diff)

    disjoint_same = DisjointSet(same_count)

    disjoint_diff = DisjointSet(diff_count)

 

    for gruop in monomial_same:

        for element in monomial_same[gruop]:

            disjoint_same.union(gruop, one_hot_encoding[element])

 

    for gruop in monomial_diff:

        for element in monomial_diff[gruop]:

            disjoint_diff.union(gruop, one_hot_encoding[element])

 

    #seperate final set

    final_same_word_set = defaultdict(set)

    final_diff_word_set = defaultdict(set)

 

    same_data = disjoint_same.data

    diff_data = disjoint_diff.data

    

    print(same_data)

    print(diff_data)

    #case ==

    for i in range(len(same_data)):

        if same_data[i] < 0:

            for j in range(len(same_data)):

                if i == same_data[j]:

                    final_same_word_set[i].add(j)

 

    #case !=

    for i in range(len(diff_data)):

        if diff_data[i] < 0:

            for j in range(len(diff_data)):

                if i == diff_data[j]:

                    final_diff_word_set[i].add(j)

 

    #convert int to string

    final_same_word_list = list()

    final_diff_word_list = list()

 

    for i in final_same_word_set:

        tmp = list()

        tmp.append(one_hot_encoding[i])

        for j in final_same_word_set[i]:

            tmp.append(one_hot_encoding[j])

        final_same_word_list.append(tmp)

 

    for i in final_diff_word_set:

        tmp = list()

        tmp.append(one_hot_encoding[i])

        for j in final_diff_word_set[i]:

            tmp.append(one_hot_encoding[j])

        final_diff_word_list.append(tmp)

 

    int_count = 0

    for i in final_same_word_list:

        for word in i:

            if str(type(word)) == "<class 'int'>":

                int_count += 1

                if int_count == 2:

                    print("1!=1")

                    sys.exit()

        int_count = 0

 

    

    #sorting

    for i in final_same_word_list:

        i.sort(key= lambda x : len(str(x)))

 

    for i in final_diff_word_list:

        i.sort(key= lambda x : len(str(x)))

 

    #for final != element(sortest)

    sortest_same_word = "abcdefghijklmnopqrstuvwxyz"

    for i in final_same_word_list:

        for j in i:

            if len(str(sortest_same_word)) >= len(str(j)):

                sortest_same_word = j

 

    sortest_diff_word = "abcdefghijklmnopqrstuvwxyz"

    for i in final_diff_word_list:

        for j in i:

            if len(str(sortest_diff_word)) >= len(str(j)):

                sortest_diff_word = j

 

    def isSortest():

        if len(final_same_word_list) != 0 and len(final_diff_word_list) != 0:

            return sortest_same_word

        elif len(final_same_word_list) == 0 and len(final_diff_word_list) != 0:

            return sortest_diff_word

    

 

    #output

    final_correct = str()

    for group in final_same_word_list:

        for word in range(1, len(group)):

            final_correct += str(group[0]) + '==' + str(group[word])

            final_correct += '&&'

 

    final_correct = final_correct[:-2]

 

    if final_diff_word_list and final_same_word_list:

        final_correct += '&&'

    for group in final_diff_word_list:

        for word in range(1, len(group)):

            if len(final_diff_word_list) == 1 and len(final_same_word_list) == 0:

                print("1==1")

                sys.exit()

            final_correct += str(group[0]) + '!=' + str(isSortest())

            final_correct += '&&'

    if final_diff_word_list and final_same_word_list:       

        final_correct = final_correct[:-2]

 

    print(final_correct)