글 읽기 - [python3] problem 주석이 맞는지 아닌지 모르겠습니다.

rhsek123 2년 전 0

안녕하세요,

어지간하면 질문의 글을 보거나

스스로 반례를 찾아서 어디가 틀렸는지 찍어보는데

"([)."

"[(]."

"[((]."

"[))]."

"([)]."

"((."

"))."

"[[."

와 예제 이상없이 출력이 되어서 질문 남겨봅니다.

처음에 stack을 이용해서 썼습니다만,

예제의 문장 끝 부분이 "."으로 끝나는 걸 보고

deque로 이용해서 재구현했는데, 같은 지점에서 틀립니다.

주석에 Problem이라는 부분이 맞는지 아닌지 잘 모르겠습니다. 이 부분에 확신이 없습니다.

그걸 쓴 이유는 바로 위 if 때문에 썼습니다.

뭐가 문제인지 알려주시면 감사하겠습니다.

from collections import deque
from sys import stdin
input = stdin.readline
n = input().rstrip("\n") 

tmp=tmp1=0
while(n!="."):
    l = deque(list(n))
    cnt_1 = cnt = 0
    while(l[0]!="."):
        tmp = l.popleft()

        # "[]" "[" 가 나오면 cnt_1을 +1, "]"일 때 cnt_1 -1
        if tmp=='[':
            cnt_1+=1
            tmp1=tmp
        elif tmp=="]":
            cnt_1-=1

        # "()" "()" 가 나오면 cnt_1을 +1, ")"일 때 cnt_1 -1
        if tmp=='(':
            tmp1=tmp
            cnt+=1
        elif tmp==")":
            cnt-=1

        # ( 혹은 [ 보다, ), ]이 한번이라도 더 많이 나올 경우 균형이 불가능
        # "no", break
        if cnt_1 < 0 or cnt < 0:
            print("no")
            break
                
        # "[qqdq)" or "(dqdqw]" 같은 경우에 대한 처리
        if (tmp1=="[" and tmp==")") or (tmp1=="(" and tmp=="]"):
            print("no")
            break
         
        # problem ! : "(([]))" -> 아래를 해주지 않으면 바로 위의 if 때문에 왼쪽 같은 경우가 "no"
        if (tmp1=="[" and tmp=="]") or (tmp1=="(" and tmp==")"):
            tmp1 = 0
        
        if l[0]==".":
            if cnt==0 and cnt_1==0:
                print("yes")
            else:
                print("no")
                
    n = input().rstrip("\n") 

twicedtna 2년 전 1

제가 생각하는 문제는 스택을 쓰지 않아서 질문자분 프로그램이 과거에 나왔던 여는 괄호들의 순서를 기억할 수 없다는 점이에요.

코드를 잘 보시면 결국 프로그램이 기억하는 건 바로 직전의 여는 괄호 딱 하나만 tmp1에 기억하고 있습니다.

그래서 tmp1에 기억하고 있는 여는 괄호가 완성되면 tmp1=0이 되니까 그 이전의 여는 괄호가 뭐였는지는 평생 모릅니다.

밑에 반례를 보시면 처음으로 잘못된 괄호가 나오는 부분에서 tmp1==0 이기 때문에 34줄의 if 조건을 제대로 수행할 수 없습니다.

반례
(( [[ ]) ]).

정답: no
질분자분 코드 출력: yes

rhsek123 2년 전 1

답변 감사합니다.

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

문제

문제

출처

ICPC

[python3] problem 주석이 맞는지 아닌지 모르겠습니다.

rhsek123 2년 전 0

twicedtna 2년 전 1

rhsek123 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말