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

기존 포스트

https://seungbok3240.tistory.com/51?category=819423

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

문제점

> 코드가 길어지다보니 나 자신조차 머릿속에서 생각이 꼬여버렸다.

> 다시 처음부터 풀었다.

> 코드를 다 짜고 보니 예제는 알맞게 출력되지만 질문검색 사이트에서 찾은 반례가 통과되지 않는 문제점을 알았다.

https://www.acmicpc.net/board/view/28572

글 읽기 - 제가 만든 예제 output 맞는지 확인좀 해주세요.

> 반례를 토대로 코드를 수정하여야겠다.

 

코드

import sys, copy

from collections import defaultdict

 

input = sys.stdin.readline

 

class DisjointSet:

    def __init__(self,n):

        self.data = list(range(n))

        self.size = n

 

    def find(self, index):

        return self.data[index]

 

    def union(self,x,y):

        x, y = self.find(x), self.find(y)

 

        if x ==y:

            return

 

        for i in range(self.size):

            if self.find(i) == y:

                self.data[i] = x

        

    @property

    def length(self):

        return len(set(self.data))

 

if __name__ == "__main__":

    print("==========================INPUT===========================")

    S = input().strip('\n')

 

    logic_list = S.split('&&')

    

    same = list()

    diff = list()

    

    def isInt(word):

        try:

            word = int(word)

            return word             #word == int

        except ValueError:

            return word             #word == string

    

    #split same group and diff group

    for monomial in logic_list:

        if '==' in monomial:

            tmp = monomial.split('==')

            tmp[0] = isInt(tmp[0])

            tmp[1] = isInt(tmp[1])

 

            same.append(tmp)

        elif '!=' in monomial:

            tmp = monomial.split('!=')

            tmp[0] = isInt(tmp[0])

            tmp[1] = isInt(tmp[1])

            diff.append(tmp)

    

    print("=============================================================")

    print("same : ", same)

    print("diff : ", diff)            

 

    #one-hot-encoding

    one_hot_encoding = defaultdict(set)

    

    def do_one_hot_encoding(same, diff, one_hot_encoding):

        count = 0

        for group in same:

            for word in group:

                if word not in one_hot_encoding:

                    one_hot_encoding[word] = count

                    one_hot_encoding[count] = word

                    count += 1

 

        for group in diff:

            for word in group:

                if word not in one_hot_encoding:

                    one_hot_encoding[word] = count

                    one_hot_encoding[count] = word

                    count += 1

        

        return one_hot_encoding, count

    

    one_hot_encoding, count = do_one_hot_encoding(same,diff,one_hot_encoding)

    print("===========================One-hot-encoding===========================")

    print("one-hot-encoding : ", one_hot_encoding)

 

    #convert string to int

    same_int = list()

    diff_int = list()

 

    for group in same:

        tmp = list()

        for word in group:

            tmp.append(one_hot_encoding[word])

        same_int.append(tmp)

    

    for group in diff:

        tmp = list()

        for word in group:

            tmp.append(one_hot_encoding[word])

        diff_int.append(tmp)

 

    #a==a같은 식이 있다면 식에서 생략

    same_int_copy = copy.deepcopy(same_int)

    index_count = 0

    for group in same_int_copy:

        if group[0] == group[1]:

            del same_int[index_count]

        index_count += 1

 

    #a!=a같은 식이 있다면 1!=1(false)를 출력하고 시스템 종료

    diff_int_copy = copy.deepcopy(diff_int)

    index_count = 0

    for group in diff_int_copy:

        if group[0] == group[1]:

            print("1!=1")

            sys.exit()

        index_count += 1

    

    print("===========================String to int===========================")

    print("same_int : ", same_int)

    print("diff_int : ", diff_int)

 

    # make Disjoint set

    disjoint_same = DisjointSet((len(same_int) + len(diff_int)) * 2)

    disjoint_diff = DisjointSet((len(same_int) + len(diff_int)) * 2)

 

    for group in same_int:

        disjoint_same.union(group[0], group[1])

    

    for group in diff_int:

        disjoint_diff.union(group[0], group[1])

 

    print("===========================삭제하기 전=============================")

    print("same data : ", disjoint_same.data)

    print("diff data : ", disjoint_diff.data)

 

    '''

    for i in range((len(same_int) + len(diff_int)) * 2):

        check_count_same = disjoint_same.data.count(i)

        check_count_diff = disjoint_diff.data.count(i)

        if check_count_same == 1:

            disjoint_same.data.remove(i)

        if check_count_diff == 1:

            disjoint_diff.data.remove(i)

 

    print("===========================삭제한 후==============================")

    print("same data : ", disjoint_same.data)

    print("diff data : ", disjoint_diff.data)

    '''

 

    final_same = defaultdict(set)

    final_diff = defaultdict(set)

 

    #Int to string

    for i in range(len(disjoint_same.data)):

        word_count = disjoint_same.data.count(disjoint_same.data[i])

        if word_count == 1:

            continue

        final_same[disjoint_same.data[i]].add(one_hot_encoding[i])

    

    for i in range(len(disjoint_diff.data)):

        word_count = disjoint_diff.data.count(disjoint_diff.data[i])

        if word_count == 1:

            continue

        final_diff[disjoint_diff.data[i]].add(one_hot_encoding[i])

 

    print("===========================Int to string=========================")

    print("final_same : ", final_same)

    print("final_diff : ", final_diff)

 

    correct_same_list = list()

    for group in final_same:

        tmp = list()

        for word in final_same[group]:

            tmp.append(word)

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

        correct_same_list.append(tmp)

    

    correct_diff_list = list()

    for group in final_diff:

        tmp = list()

        for word in final_diff[group]:

            tmp.append(word)

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

        correct_diff_list.append(tmp)

 

    print("========================final group list=========================")

    print("correct_same_list : ", correct_same_list)

    print("correct_diff_list : ", correct_diff_list)

 

    #more then two int in a group --> false!!!

    int_count = 0

    for group in correct_same_list:

        for word in group:

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

                int_count += 1

            if int_count == 2:

                print("1!=1")

                sys.exit()

        int_count = 0

 

    #for final != element(sortest)

    sortest_same_word = "abcdefghijklmnopqrstuvwxyz"

    for i in correct_same_list:

        if len(str(sortest_same_word)) > len(str(i[0])):

            sortest_same_word = i[0]

 

    sortest_diff_word = "abcdefghijklmnopqrstuvwxyz"

    for i in correct_diff_list:

        if len(str(sortest_diff_word)) > len(str(i[0])):

            sortest_diff_word = i[0]

 

    def isSortest():

        if len(correct_same_list) != 0 and len(correct_diff_list) != 0:

            return sortest_same_word

        elif len(correct_same_list) == 0 and len(correct_diff_list) != 0:

            return sortest_diff_word

 

    #final output

    final_output = str()

    for group in correct_same_list:

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

            final_output += str(group[0]) + '==' + str(group[word_index])

            final_output += '&&'

    

    final_output = final_output[:-2]

 

    if correct_diff_list and final_output:

        final_output += '&&'

        for group in correct_diff_list:

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

                final_output += str(group[0]) + '==' + str(isSortest())

                final_output += '&&'

        final_output = final_output[:-2]

    else:

        for group in correct_diff_list:

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

                final_output += str(group[0]) + '==' + str(isSortest())

                final_output += '&&'

        final_output = final_output[:-2]

 

    print("========================final output============================")

    if final_output:

        print("final output : ", final_output)

    else:

        print("1==1")