글 읽기 - 도저히 반례를 찾지 못하겠습니다. 도와주세요ㅠㅠ

gibiee 5년 전 0

카카오 코드 페스티벌 2018 예선 대회의 C번 숏코딩 문제입니다.

우선 코드를 간결하게 짜지 못해서 죄송합니다. 처음부터 각종 예외들을 생각하지 못하고 하나씩 예외처리하다보니 코드가 너무 난잡해졌네요...

게다가 제가 파이썬을 공부한지 얼마 되지 않아 스킬이 많이 부족합니다. 죄송합니다.ㅠㅠ

구현한 알고리즘은 다음과 같습니다.

- "==" 로 파싱한 변수들을 같은 것들끼리 배열으로 모아서 same 배열에 저장시킴( same 배열은 결국 2차원 배열 )

- "!=" 인 부분은 통째로 문자열으로 not_same 배열에 저장시킴 ( not_same 배열은 결국 1차원 배열 )

- 각각의 변수들은 그보다 길이가 짧은 변수로 대체할 수 있는지 검사.

- 항상 True인 경우는 "3==3" 으로 출력, 항상 False 인 경우는 "2==3" 으로 출력.

- 각종 예외처리 (중복제거, a!=a 인 경우 등등...)

문제의 예제는 물론이고 질문 게시판들의 예제나 제가 직접 만든 예제들을 테스트해보았지만 모두 정상출력됩니다.

(참고가 되실까하여)채점 시에는 % 조차 표시되지 않고 바로 틀렸습니다가 표시됩니다.

제 코드가 잡아내지 못한 반례가 무엇이 있을까요? 고수님들 부탁드리겠습니다...

@djm03178 님께서 이 문제에 친절히 답변을 많이 해주시는 것을 보고 염치없지만 부탁드리겠습니다...감사합니다.

def insert_elm(s_list, vari):
    for elm in s_list:
        if vari[0] in elm and vari[1] in elm : return s_list
        elif vari[0] in elm and vari[1] not in elm :
            elm.append(vari[1])
            return s_list
        elif vari[1] in elm and vari[0] not in elm :
            elm.append(vari[0])
            return s_list

    s_list.append(vari)
    return s_list

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

def sorted_list(s_list):
    r_list = list()
    for elm in s_list:
        if elm == []: continue
        elm = sorted(elm, key=len)
        r_list.append(elm)

    return r_list

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

def search_num(same, index) :
    if index == -1 : return -1

    for i in same[index] :
        if is_num(i) == True : return i
    return -1

# f = open("15956.txt", 'r')
# input = f.readline().strip().split('&&')
input = input().strip().split('&&')

same = [[]]
not_same = list()

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

    else:  # ==인 경우
        vari = i.split('==')
        if vari[0]!=vari[1] : same = insert_elm(same, vari) # 둘이 같은 변수이면 생략한다.

# 길이 순으로 정렬
same = sorted_list(same)

# not_same의 중복 제거
not_same = list(set(not_same))

try:
    # 예외 : 서로 다른 숫자 두 가지가 존재할 경우 False
    for elm in same:
        s_count = 0
        for i in elm :
            if is_num(i) == True : s_count += 1
            if s_count >= 2 : raise

    # 예외 : 한 변수가 서로 다른 elm에 존재할 경우
    for elm in same :
        for i in elm :
            count = 0;
            for elm_2 in same :
                if i in elm_2 : count+=1
                if count >=2 : raise

    # 짝 짓기
    sentence = ''
    for elm in same:
        for i in elm:
            if i == elm[0]: continue
            sentence += elm[0] + '==' + i + '&&'

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

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

        # 조건1 : 변수가 같은 same에 있는지 검사
        vari_0 = search_index(same, vari[0])
        vari_1 = search_index(same, vari[1])
        if vari_0 != -1 and vari_1 != -1 and vari_0 == vari_1 : raise

        # 조건2 : 서로 다른 숫자 a!=b 일 때는 그냥 생략
        if is_num(vari[0]) == False : vari_0_num = search_num(same, vari_0)
        else : vari_0_num = vari[0]
        if is_num(vari[1]) == False : vari_1_num = search_num(same, vari_1)
        else : vari_1_num = vari[1]

        if vari_0_num != -1 and vari_1_num != -1 :
            if vari_0_num == vari_1_num : raise
            else : continue

        # 더 짧은 변수명으로 변경 가능한지 확인
        if vari_0 != -1 : vari[0] = same[vari_0][0]
        if vari_1 != -1 : vari[1] = same[vari_1][0]

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

    sentence_2 = list(sentence_2)
    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")

# f.close()

dotorya 5년 전 2

a!=b&&c!=d&&a!=c&&b!=d&&a==d&&b==c
->
a==d&&b==c&&a!=b&&a!=b

가 출력되네요.

정답은 a==d&&b==c&&a!=b 등입니다.

a!=b 같은 수식들의 중복체크가 완벽하지 않으신 것 같습니다.

jh05013 5년 전 1

list에서 for루프를 돌릴 때 그 안에서 list를 변형하는 건 매우 위험합니다. 0번째 원소, 1번째 원소, ...를 차례대로 보기 때문에 원소가 중간에 생략될 수 있습니다.

L = [1, 2, 3, 4, 5]
for x in L:
    L.remove(x)
print(L)

gibiee 5년 전 1

@dotorya 앗, 반례를 찾아주셔서 감사합니다. not_same의 중복제거 알고리즘 중에 오류가 있네요.

jh0513님이 지적해주신 부분과 연관지어서 수정해보도록 하겠습니다.

@jh05013 사실 코드를 짜면서 생각했던 부분입니다. 120번 줄의 not_same 중복제거 알고리즘을 말씀하시는 것 같은데요.

2차원 배열의 중복제거를 하려니 마땅한 방법이 생각나지 않아 이중for문을 돌렸더니 저런 맹점이 있네요.

2차원 배열의 중복제거를 쉽게 할 수 있는 방법이 없을까요? 검색해보니 튜플로 변환 후 numpy 라이브러리를 이용해서 다시 배열로 변환하는 방법이 있던데 그게 가장 쉬운 방법인가요?

jh05013 5년 전 1

BOJ는 numpy를 지원하지 않습니다.

이 코드를 전부 읽어서 파악하기는 쉽지 않은데, "2차원 배열의 중복 제거"가 정확히 무엇인가요?

gibiee 5년 전 1

@jh05013 2차원 배열의 중복제거라고 하니 이해하기가 쉽지 않군요.

배열 안에 배열을 가지고 있는 경우입니다.

[['a', 'b'], ['b', 'a'], ['b', 'a'], ['a', 'b']]

다음 경우에 중복제거를 하여 [['a', 'b']] 만 남기는 것입니다.

지금은 질문의 소스코드를 수정했는데요.

126, 127번 줄을 보시면 중복인 부분에 임시로 '?' 문자로 처리를 하여 나중에 결과에서 제외시키는 방법을 사용하였습니다.

jh05013 5년 전 1

sentence_2를 아예 처음부터 set()으로 둔 다음, 추가하기 전에 vari[0] < vari[1]인지 확인해서 둘을 교환하고, append([vari[0],vari[1]]) 대신 add((vari[0],vari[1]))를 하는 것이 가장 간단할 것 같습니다.

gibiee 5년 전 1

@jh05013 감사합니다. 말씀해주신대로 하니 중복제거 알고리즘이 필요가 없어져서 코드가 더 간결해지네요.

여전히 채점결과는 틀렸습니다이지만요ㅠㅠ

나중에 "==" 부분도 set을 이용해서 코딩해봐야겠습니다.

gibiee 5년 전 0

혹시 질문 보고 계시는 분들에게 유용하지 않을까 싶어 적어 놓습니다.

코드 수정 중에 발견한 반례입니다.

a==b&&c==d&&b==c 라고 입력했을 경우 a,b,c,d 가 모두 같은 집합에 있어야합니다. 저의 경우는 그렇지 못하네요.

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

문제

문제

출처

ICPC

도저히 반례를 찾지 못하겠습니다. 도와주세요ㅠㅠ

gibiee 5년 전 0

dotorya 5년 전 2

jh05013 5년 전 1

gibiee 5년 전 1

jh05013 5년 전 1

gibiee 5년 전 1

jh05013 5년 전 1

gibiee 5년 전 1

gibiee 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말