글 읽기 - 파이썬3 시간초과 도와주세요 @.@

gibiee 5년 전 0

왜 시간초과가 나오는지 모르겠습니다ㅠㅠ

전체 코드에서 이중for문 한 번 시행하고 단일for문 두 번 시행합니다.

사용한 함수들도 단일for문으로만 시행합니다.

왜 시간초과가 나는 것인지 아무리 생각해봐도 알 수가 없네요...고수님들 도와주세요.

파이썬3 로 채점 시 → 8% 에서 시간초과

PyPy3 로 채점 시 → 13% 에서 시간초과

import sys

def sorted_set(same):
    imsi_list = list()
    for elm in same:
        elm = list(elm)
        elm = sorted(elm, key=len)
        imsi_list.append(elm)
    return imsi_list

def search_index(same, vari):
    index = 0
    for elm in same :
        if vari in elm : return index
        index += 1
    return 'no'

def is_num(num):
    try:
        int(num)
        return True
    except:
        return False

def search_num(same, index) :
    if index == 'no' : return 'no'
    for i in same[index] :
        if is_num(i) : return i
    return 'no'

input = sys.stdin.readline().rstrip().split('&&')

same = list(set())
not_same = set()

try:

    for i in input:
        if i.find('==') == -1 :  # != 인 경우
            vari = i.split('!=')

            if vari[0] == vari[1] :  # 둘이 같은 변수라면 False출력
                raise Exception
            else :
                not_same.add((vari[0], vari[1]) if vari[0] < vari[1] else (vari[1],vari[0]))

        else :  # ==인 경우
            vari = i.split('==')
            vari0_index = search_index(same, vari[0])
            vari1_index = search_index(same, vari[1])
            if vari0_index == 'no' and vari1_index == 'no' : # 둘 다 없으면 통째로 추가
                same.append( { vari[0],vari[1] } )
            else : # 둘 중 적어도 하나는 인덱스가 있는 경우
                if vari0_index == vari1_index : # 둘의 인덱스가 같으면 무시
                    continue
                elif vari0_index != 'no' and vari1_index != 'no' : # 둘 다 인덱스가 있고 값이 다르면 합집합
                    same[vari0_index] = same[vari0_index].union(same[vari1_index])
                    del same[vari1_index]
                elif vari0_index != 'no' : # vari[0]이 인덱스를 가지고 있는 경우
                    same[vari0_index] = same[vari0_index].union( {vari[1]} )
                else : # vari[1]이 인덱스를 가지고 있는 경우
                    same[vari1_index] = same[vari1_index].union( {vari[0]} )

    same = sorted_set(same) # 길이 순으로 정렬
    not_same = list(not_same)

    # !=의 경우 같은 것을 찾아서 치환
    sentence_2 = set()
    for vari in not_same :
        vari = list(vari)

        # 더 짧은 변수명으로 변경 가능한지 확인
        vari0_index = search_index(same, vari[0])
        vari1_index = search_index(same, vari[1])
        if vari0_index != 'no' : vari[0] = same[vari0_index][0]
        if vari1_index != 'no' : vari[1] = same[vari1_index][0]

        # 조건1 : 서로 같은 변수일때 ( a!=a ) False 출력
        if vari[0] == vari[1] : raise

        # 조건3 : 서로 다른 숫자 a!=b 일 때는 그냥 생략
        if is_num(vari[0]) : vari0_num = vari[0]
        else : vari0_num = search_num(same, vari0_index)
        if is_num(vari[1]) : vari1_num = vari[1]
        else : vari1_num = search_num(same, vari1_index)
        #vari_index가 'no' 일 때는 search_num에서 'no' 반환

        if vari0_num != 'no' and vari1_num != 'no' : # 둘 다 'no'이 아닐 때 : 대응되는 숫자가 있을 때
            if vari0_num == vari1_num : # 같은 숫자 ex) 11 != 11 인 경우 False 출력
                raise
            else : continue # 다른숫자 ex) 11 != 12 인 경우 그냥 무시.

        sentence_2.add((vari[0],vari[1]) if vari[0] < vari[1] else (vari[1],vari[0]))

    
    sentence = ''
    for elm in same:
        s_count = 0
        for i in elm :
            if is_num(i) : # "=="인 경우 예외1 : 서로 다른 숫자 두 가지가 한 집합에 존재할 경우 False
                s_count += 1
                if s_count >= 2 : raise
            # "=="인 경우 짝 짓기
            if i == elm[0] : continue 
            else : sentence += elm[0] + '==' + i + '&&'

    result = sentence;
    for i in sentence_2 : result += i[0] + "!=" + i[1] + "&&"

    if result == '' : print("3==3") # True
    else : print(result[:-2])

except Exception:   # False
    print("2==3")

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

문제

문제

출처

ICPC

파이썬3 시간초과 도와주세요 @.@

gibiee 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말