2020 동계 학습 동아리_4회차_2020-02-10(월)

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

15956번: 숏코딩

카카오 코드 페스티벌 C번 문제를 풀어보았다. 하지만 시간초과로 인해 정답 코드를 도출해내지 못하였다.

시간초과가 나는 이유를 생각해봤을때 무분별한 for문의 사용이 아닐까 짐작하고 있다.

원래 D번 문제인 부스터도 풀어야하지만 시간이 부족하여 문제를 보지 못했다.

 

해결 방법

> '=='인 그룹과 '!='인 그룹을 나눈다.

> 각 그룹 안에서도 또 다른 그룹을 나눈다.(같은거 안에 같은거...)

> '!='에 속한 그룹의 단어들이 '==' 그룹의 단어(더 짧은)로 바뀌는지 확인하고 연산한다.

> 출력!!!

 

코드

import sys

 

def end():

    print("1==2")

    sys.exit(0)

 

def isNum(word):

    try:

        word = int(word)

        return True

    except:

        return False

 

same = []

same_word_index = dict()

same_int_index = dict()

diff = set()

 

S = sys.stdin.readline().strip().split('&&')

 

count = 0

#split same group and diff group

for i in S:

    if '==' in i:

        tmp = i.split('==')

        if tmp[0] != tmp[1]:    #조건 : 서로 같은 문자나 숫자가 a==a일때는 True이므로 생략가능

            x , y = same_word_index.get(tmp[0]), same_word_index.get(tmp[1])

            if x == None and y == None:

                same_word_index.setdefault(tmp[0],count)

                same_word_index.setdefault(tmp[1],count)

                if isNum(tmp[0]): same_int_index[count] = tmp[0]

                elif isNum(tmp[1]): same_int_index[count] = tmp[1]

                same.append({tmp[0], tmp[1]})

                count += 1

            elif x != None and y == None:

                same[x].add(tmp[1])

                same_word_index.setdefault(tmp[1],x)

                if isNum(tmp[1]):

                    if same_int_index.get(x) == None: same_int_index[x] = tmp[1]

                    else: end()

            elif y != None and x == None:

                same[y].add(tmp[0])

                same_word_index.setdefault(tmp[0],y)

                if isNum(tmp[0]):

                    if same_int_index.get(y) == None: same_int_index[y] = tmp[0]

                    else: end()

            else:

                if x == y:

                    continue

                if isNum(tmp[0]) and isNum(tmp[1]): end()

                same[x] = same[x].union(same[y])

                for word in same[y]:

                    same_word_index[word] = x

                same[y] = []

                if same_int_index.get(x) == None and same_int_index.get(y) != None:

                    same_int_index[x] = same_int_index.get(y)

                    same_int_index[y] = None

    else:

        tmp = i.split('!=')

        if tmp[0] == tmp[1]:    #조건 : 서로 같은 문자나 숫자가 a!=a일때는 False이므로 1==2 출력 후 시스템 종료

            end()

        diff.add((tmp[1], tmp[0]))

 

#sort 

for i in range(len(same)):

    same[i] = list(same[i])

    same[i].sort(key= len)

 

final_diff = set()

for group in diff:

    group = list(group)

    for i in same:

        if group[0] in i and group[1] in i: #조건 : a!=b일때 a와b가 same의 같은 그룹일때 ---> False

            end()

        if group[0] in i:

            if len(str(group[0])) < len(str(i[0])): #조건 : diff 그룹의 단어가 same의 그룹의 다른 단어로 교체 가능

                pass

            else:

                group[0] = i[0]

        if group[1] in i:

            if len(str(group[1])) < len(str(i[0])):

                pass

            else:

                group[1] = i[0]

    if group[0] == group[1]:  #조건 : 바뀐 단어가 서로 같을때 ---> False

        end()

    if isNum(group[0]) and isNum(group[1]):   #조건 : 바뀐 단어가 둘 다 int일때

        if group[0] == group[1]:              #같다면 False

            end()

        else:              #다르다면 생략가능

            continue

    final_diff.add((group[0], group[1]))

 

#output

answer = str()

for group in same:

    for word in group:

        if word == group[0]:

            continue

        answer += str(group[0]) + '==' + str(word) + '&&'

 

for group in final_diff:

    group = list(group)

    answer += group[0] + '!=' + group[1] + '&&'

 

if not answer:

    print("1==1")

else:

    print(answer[:-2])