[파이썬] 백준 28709 : 와일드카드 괄호 문자열 (골드1)

[파이썬] 백준 28709 : 와일드카드 괄호 문자열 (골드1)

28709번: 와일드카드 괄호 문자열

---

문제

---

풀이

0. 방향성 생각

• *이 있는 케이스와 없는 케이스로 나눈다.
• 왜 와이 - > 입력 문자열 S를 split('*')을 통해 나누면 항상 다음의 케이스로 나누어진다.
• S = *A꼴 -> string = ['',A] : 왼쪽에서 '('를 무한정 공급 가능하다. 뒤에서부터 순회해서 (개수가 ?)개수랑 일치시킨다.
• S = A*꼴 -> string = [A,''] : 오른쪽에서 ')'를 무한정 공급 가능하다. 순회해서 (?개수가 )개수랑 일치시킨다.
• S = *A*꼴 -> string = ['',A,''] : 항상 올바른 문자열이므로 체크할 필요가 없다.
• S = A*B꼴 -> string = [A,B] : case1과 case2 경우가 동시에 있는 경우.
• S = S (별이 없는 경우)
• 위 4가지 케이스에 대해서는 별표가 존재하고 이 때 따로 처리를 해준다.
• *이 존재하는 경우 리스트의 맨 앞, 뒤만 체크하면 된다.

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

2. *이 없는 경우 문자열 처리 함수 정의

def nstar(s):
    
    if s[0] == ')' or s[-1] == '(':
        return False

    l,m,r = 0,0,0
    for i in s:
        if i == '(': l += 1
        elif i == ')': r += 1
        else: m += 1
    
    leng = len(s)
    if l > leng//2 or r > leng//2:
        return False

    count = 0
    for i in s:
        if i == '?':
            if l < leng//2:
                i = '('
                l += 1
            else:
                i = ')'

        if i == '(': count += 1
        else: count -= 1
        
        if count < 0:
            return False
    return True

• 양 끝이 )이거나 (이면 올바른 문자열이 아니다.
• ( 혹은 )의 개수가 절반 이상이면 올바른 문자열을 만들 수 없다. (매칭 불가)
• 절반을 나눠서 앞쪽은 (로, 뒤쪽을 )로 치환
• ( 개수가 절반이 되기 전까지 ?는 계속 (로 치환한다. 넘어가면 )로 치환한다.

3. *이 왼쪽에 있는 경우 문자열 처리 함수 정의

def lstar(s):
    q = deque(s)
    count = 0
    while q:
        x = q.pop()
        if x == '(': count -= 1
        else: count += 1
        if count < 0: return False
    return True

• S = *A꼴, A의 왼쪽에 별이 존재하는 경우 문자열 처리
• 왼쪽에서 무한정 (을 공급할 수 있다. ?) 개수가 (보다 많아야한다. 많아지면 *로 처리가능함

3. *이 오른쪽에 있는 경우 문자열 처리 함수 정의

def rstar(s):
    q = deque(s)
    count = 0
    while q:
        x = q.popleft()
        if x == ')': count -= 1
        else: count += 1
        if count < 0: return False
    return True

• S = A*꼴, A의 오른쪽에 별이 존재하는 경우 문자열 처리
• 오른쪽에서 무한정 )을 공급할 수 있다. (? 개수가 )보다 많아야한다. 많앚이면 *로 처리가능함

5. 출력

for _ in range(int(input())):

    string = input().split("*")
    length = len(string)

    if length == 1:
        if len(string[0])%2: correct = False
        else: correct = nstar(string[0])

    elif length > 1:
        s0,s1 = string[0], string[-1]

        if s0 == '' and s1 == '': correct = True #  string = *

        elif s0 == '' and s1 != '': correct = lstar(s1) # string = *A

        elif s0 != '' and s1 == '': correct = rstar(s0) # string = A*

        elif s0 != '' and s1 != '': correct = rstar(s0) and lstar(s1) # string = A*B

    if correct: print('YES')
    else: print('NO')

• split으로 문자열을 substring으로 나누고 양 끝만 체크한다.
• *이 없는경우 (?)로만 이루어져있다. 이 때 길이가 짝수가 아니면 올바른 문자열을 만들 수 없다
• 짝수인 경우 nstar를 통해 체크한다.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

def nstar(s):
    
    if s[0] == ')' or s[-1] == '(':
        return False

    l,m,r = 0,0,0
    for i in s:
        if i == '(': l += 1
        elif i == ')': r += 1
        else: m += 1
    
    leng = len(s)
    if l > leng//2 or r > leng//2:
        return False

    count = 0
    for i in s:
        if i == '?':
            if l < leng//2:
                i = '('
                l += 1
            else:
                i = ')'

        if i == '(': count += 1
        else: count -= 1
        
        if count < 0:
            return False
    return True

def lstar(s):
    q = deque(s)
    count = 0
    while q:
        x = q.pop()
        if x == '(': count -= 1
        else: count += 1
        if count < 0: return False
    return True

def rstar(s):
    q = deque(s)
    count = 0
    while q:
        x = q.popleft()
        if x == ')': count -= 1
        else: count += 1
        if count < 0: return False
    return True


for _ in range(int(input())):

    string = input().split("*")
    length = len(string)

    if length == 1:
        if len(string[0])%2: correct = False
        else: correct = nstar(string[0])

    elif length > 1:
        s0,s1 = string[0], string[-1]

        if s0 == '' and s1 == '': correct = True #  string = *

        elif s0 == '' and s1 != '': correct = lstar(s1) # string = *A

        elif s0 != '' and s1 == '': correct = rstar(s0) # string = A*

        elif s0 != '' and s1 != '': correct = rstar(s0) and lstar(s1) # string = A*B

    if correct: print('YES')
    else: print('NO')

 

코멘트

별표 없는 경우가 굉장히 까다로웠던.... 처음에 스택으로 처리하려고 했는데 하나 고치면 자꾸 반례가 생겨서 개수세는 식으로 바꿨는데도 실패...

solved.ac - solved.ac Grand Arena #2

해설이 있는줄 모르고 한달넘게 고민... 매일 고민한건 아니지만 매주 1트는 했던거같은데 참고해서 성공

해설 방식처럼 치환하는게 항상 정답을 보장하냐에 대해서는 잘 모르겠어서 접근을 안했었는데 맞다네요.... 흠....