📣 솔브드 그랜드 아레나 📣

 

 

 

솔브드에서 하는 그랜드 아레나 참가했다

그래도 나름 알고리즘 공부 열심히 해서

3솔은 할 줄 알았는데

.....2솔 했다

그것도 브론즈로 2개 풀었다

보니까 나머지 문제는 다 골드에서 다이아더라

실버 달라구여 실버 (찡찡)

 

암튼 내 실력을 여실히 깨닫고 낑낑댔던 문제(I번) 오답 노트나 하련다...

 

우선 나온 문제들 유형을 간단하게 살펴봤는데 역시나 그래프랑 트리 문제가 대부분을 차지했다.

수학 문제랑 그리디 문제도 꽤나 나왔다.

이제 곧 SUAPC Summer 나갈 건데 그전에 트리 공부 좀 더 해놔야겠다.

 

 

앞에 쉬운 두 문제를 30분컷 하고 나서 이 문제만 2시간 반이나 붙들고 있었는데 결국 못 풀었다.

https://www.acmicpc.net/problem/28709

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

 

일단 보자마자 예전에 비슷한 문제 스택으로 풀었던 게 생각나서

스택으로 풀기 시작!

 

word에 입력값 넣기

 

word에서 하나씩 pop해서 스택에 넣을지 말지 판별( word 빌 때까지 반복 )

 

"("  "*"  "?" 는 스택에 바로 집어넣고

")" 는 스택이 비어있으면 바로 NO 출력하고 return

스택이 비어있지 않으면 스택의 top 확인해서 "(" 면 pop해주기

 

 while 문 빠져나왔을 때

스택이 비어있으면 YES 출력

스택 안에 남아있는 게   ["("   ->   "*" / "?" ] 이런 순서면 YES 아니면 NO 출력

 

import sys
input = sys.stdin.readline
word = []

n = int(input())


def mirror(word):
    word.pop(-1)
    stack = []
    while word:
        curr = word.pop(0)
        if curr == "(" or curr == "?" or curr == "*":
            stack.append(curr)
        else:
            if len(stack) > 0:
                if stack[-1] == "(":
                    stack.pop(-1)
                elif stack[-1] == "?" or stack[-1] == "*":
                    continue
            else:
                print("NO")
                return

    if len(stack) == 0:
        print("YES")
        return
    else:
        if stack[-1] == "?" or stack[-1] == "*":
            print("YES")
            return
        else:
            print("NO")
            return


for i in range(n):
    word = list(input())
    mirror(word)
    word.clear()

 

아니 근데 문제 잘못 읽어서( ? 랑 * 차이 완전 무시하고 풀어버림... )

시간 허비를 엄청나게 했다.

이건 막판에 멘붕 와서 갈아엎은 코드...

 

import sys
input = sys.stdin.readline
word = []
Yes = [[], ["*"], ["*"], ["(", "?", "*"]]
global ans
ans = True

n = int(input())


def mirror(word):
    print(word)
    global ans
    stack = []
    while word:
        curr = word.pop(0)
        if curr == "(" or curr == "*" or "?":
            stack.append(curr)
            print(stack)
        else:
            if len(stack) > 0:
                if stack[-1] == "(" or "?":
                    stack.pop(-1)
                    print(stack)
                else:
                    stack.append(curr)
                    print(stack)
            else:
                print("NO")
                return

    if len(stack) == 0:
        print("YES")
        return
    else:
        while stack:
            now = stack.pop(0)
            print(now)
            if now == "(":
                now = 0
            elif now == ")":
                now = 1
            elif now == "?":
                now = 2
            else:
                now = 3
            print(stack[0], Yes[now])
            if stack[0] in Yes[now]:
                ans = True
            else:
                ans = False

        if ans:
            print("YES")
        else:
            print("NO")


for i in range(n):
    word = list(input())
    word.pop(-1)
    mirror(word)
    word.clear()

 

근데 이 코드도 막판에 완전 큰 오류 발견해서 고치려고 했지만.. 시간이 모자랐다...

 

 

아래 코드는 솔브드에서 제공한 모범 답안

https://solved.ac/arena/2/editorial

solved.ac

import sys


def input(): return sys.stdin.readline().rstrip()


def solve(s):
    s = list(s)
    # 문자열에 '*' 이 있는 경우
    if s.count('*') >= 1:
        cnt = 0
        for c in s:
            if c == '*':   # A : 첫 '*'이 나타날 때까지의 문자열
                break
            if c == ')':
                cnt -= 1
            else: 
                cnt += 1   #'?' -> '(' 취급
            
            # cnt가 음수가 되는 순간(짝을 이루지 못한 ')'가 등장하는 순간) False 반환 
            if cnt < 0:
                return False
                
        cnt = 0
        for c in s[::-1]:
            if c == '*':    # C : 문자열 끝에서부터 마지막 '*'까지의 문자열
                break
            if c == '(':
                cnt -= 1
            else:			# '?' -> ')' 취급
                cnt += 1
            # cnt가 음수가 되는 순간(짝을 이루지 못한 '('가 등장하는 순간) False 반환
            if cnt < 0:
                return False
        # B : A와 C를 제외한 나머지 문자열 -> 시작과 끝이 '*'로 되어 있으므로 항상 True
        # A와 C를 모두 통과했다면 True 반환
        return True
        
    # 문자열에 '*'이 포함되지 않은 경우
    
    # 문자열의 길이가 홀수인 경우 무조건 짝이 없는 '(' or ')' or '?'가 등장하므로 False 반환
    if len(s) % 2 != 0:
        return False
    open_ = s.count('(')
    close = s.count(')')
    # '('나 ')'의 개수가 문자열 길이의 반보다 많으면 False 반환 -> 짝을 못 이루는 애들이 생김
    if open_ > len(s) // 2 or close > len(s) // 2:
        return False

    cnt = 0
    for c in s:
    # '?'를 '('나 ')'로 치환 -> 이때 '('나 ')'의 개수가 문자열 길이의 반과 동일하면 해당 문자로 치환해줘선 안 된다 -> 짝을 이루지 못하게 됨
        if c == '?':
            # '?' -> '(' 먼저(그리디)
            if open_ < len(s) // 2:
                c = '('
                open_ += 1
            # '?' -> ')'
            else:
                c = ')'
        if c == '(':
            cnt += 1
        else:
            cnt -= 1
        # cnt가 음수가 되면(짝을 이루지 못하는 ')'가 생기면) False 반환
        if cnt < 0:
            return False
    return True


def main():
    T = int(input())
    for _ in range(T):
        s = input()
        print("YES" if solve(s) else "NO")


if __name__ == "__main__":
    main()

 

어렵다....

괄호 문제는 유형으로 외워두면 좋을 듯...

스택에 넣으면 너무 단편적으로 판단하고 pop해버려서 이런 복잡한 조건('?' '*')이 포함되어 있을 땐

스택을 안 쓰는 게 좋을 것 같다.

 

앞에서부터 탐색, 뒤에서부터 탐색 둘 다 하는 방법도 기억해둬야겠다.

 

평범한 괄호 문제 같은 경우는

for문으로 문자열 탐색하면서

'(' -> cnt ++

')' -> cnt --

cnt < 0 되는 순간 False 반환해버리는 식으로 풀면 될 것 같다

 

이제 괄호 문제는 안 틀릴거야아아아아🔥🔥

 

 

---

 

 

끝나고 왹파티🎉🎉🎉🎉

 

 

 

진짜 역대급으로 알차구 재밌었다...ㅎㅎㅎ