글 읽기 - 9012번 반례 도움이 필요합니다.

nj2753 4년 전 0

스택으로 풀어야하는것도 알지만

반례를 찾으면서 무식하게 코딩해봤는데요.

반례를 못찾아서 수정을 못하고 있습니다.

도움 주시면 참 감사할 것 같습니다 :(

제가 생각한 풀이는 주석으로 달아놓겠습니다.

"""
반례인 경우 전부 NO를 리턴, 반례에 해당되지 않으면 YES를 리턴.

"""


def isVPS(target):
    cnt = 0
    cnt_reverse = 0
    if len(target) % 2 != 0: # 반례1: 괄호의 수가 홀수인경우
        return 'NO'
    if target[0] != '(' or target[-1] != ')':  # 항상 '('로 시작하고 ')'끝나야함
        return 'NO'

    # First half
    for i in range(int(target.__len__() / 2)): # 처음 반에서 정방향/역방향 괄호 카운트
        if target[i] == '(':
            cnt += 1
        else:
            cnt_reverse += 1

    if cnt < cnt_reverse: # 처음 반에 역방향 괄호가 더 많으면 VPS가 아님
                          # 적어도 동수를 이뤄야 함
        return 'NO'

    first = cnt - cnt_reverse    # 처음 반에서 정방향괄호 수 - 역방향 괄호 수
                                 # 이후 후반에 역방향 괄호 수와 같아야 함.
    cnt = 0
    cnt_reverse = 0           # 카운터 초기화

    # Second half
    for i in range(int(target.__len__() / 2), target.__len__()):
        if target[i] == '(':
            cnt += 1
        else:
            cnt_reverse += 1
    if cnt > cnt_reverse:     # 정방향이 더 많으면 리턴 0
        return 'NO'
    second = cnt_reverse - cnt # 후반 역방향 괄호 수

    if first != second: # 전반에 남은 정방향 괄호 수 != 후반에 남은 역방향 괄호 수
        return 'NO'
    else:
        return 'YES'


lst = []
T = int(input())
for i in range(T):
    tmp = input()
    tmp_list = list(tmp)
    lst.append(tmp_list)

for i in range(T):
    print(isVPS(lst[i]))

bupjae 4년 전 0

다음 입력에 대해서

정답: NO

오답: YES

1
()()()()())(()

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

문제

문제

출처

ICPC

9012번 반례 도움이 필요합니다.

nj2753 4년 전 0

bupjae 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말