STUDY/Algorithm

[백준] 2504 괄호의값

sinawi95 2021. 2. 7. 01:51
728x90

www.acmicpc.net/problem/2504

 

2504번: 괄호의 값

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.  만일

www.acmicpc.net

s=input()
stack=[]
result = 0
if s.count('(') != s.count(')') or s.count('[') != s.count(']'):
    s='' #반복문 안돌리기
try:
    for ch in s:
        tmp = []
        #닫는 괄호를 만나는 경우에 여는 괄호를 만날때까지 다 꺼냄
        if ch == ']': 
            while stack!=[]:
                tmp_ch = stack.pop()
                if tmp_ch == '[':
                    break
                else:
                    tmp.append(tmp_ch)
            if tmp == []:
                stack.append(3)
            else: #tmp !=[]
                stack.append(sum(tmp)*3)
        elif ch ==')':
            while stack!=[]:
                tmp_ch = stack.pop()
                if tmp_ch == '(':
                    break
                else:
                    tmp.append(tmp_ch)
            if tmp == []:
                stack.append(2)
            else: #tmp !=[]
                stack.append(sum(tmp)*2)
        # 닫는 괄호를 만나기 전까지 stack에 다 추가함
        else:
            stack.append(ch)
        #print(stack)
    result= sum(stack)
except:
    pass
print(result)

우선 1차 시도인데 try: except: 으로 에러를 처리했더니 그냥 끝났다.

다음과 같은 에러가 뜬다. TypeError: unsupported operand type(s) for +: 'int' and 'str'

stack에 처리하지 않은 괄호들이 있어서 생기는 문제인것같다. 반례: )())((

이 문제는 마지막 부분에 sum을 사용해서 구한 부분을 stack안에 있는 값이 모두 int인경우에만 더하는 경우로 해결했다.

s=input()
stack=[]
result = 0
if s.count('(') != s.count(')') or s.count('[') != s.count(']'):
    s='' #반복문 안돌리기

for ch in s:
    tmp = []
    #닫는 괄호를 만나는 경우에 여는 괄호를 만날때까지 다 꺼냄
    if ch == ']': 
        while stack!=[]:
            tmp_ch = stack.pop()
            if tmp_ch == '[':
                break
            else:
                tmp.append(tmp_ch)
        if tmp == []:
            stack.append(3)
        else: #tmp !=[]
            stack.append(sum(tmp)*3)
    elif ch ==')':
        while stack!=[]:
            tmp_ch = stack.pop()
            if tmp_ch == '(':
                break
            else:
                tmp.append(tmp_ch)
        if tmp == []:
            stack.append(2)
        else: #tmp !=[]
            stack.append(sum(tmp)*2)
    # 닫는 괄호를 만나기 전까지 stack에 다 추가함
    else:
        stack.append(ch)
    #print(stack)

for i in stack:
    if isinstance(i, int):
        result += i
    else:
        result = 0
        break
print(result)

2차 시도도 똑같은 에러... TypeError: unsupported operand type(s) for +: 'int' and 'str'

생각해보니 반복문 내부에 있는 sum()에도 괄호가 들어갈수있을것이라 생각했고 [)(] 을 넣어보니 역시나였다.

두번째 반례:  [)(]

근데 고치고나니 원래 나와야하는 값이 안나온다...

s=input()
stack=[]
result = 0
if s.count('(') != s.count(')') or s.count('[') != s.count(']'):
    s='' 

for ch in s:
    tmp = []
    if ch == ']': 
        while stack!=[]:
            tmp_ch = stack.pop()
            if tmp_ch == '[':
                break
            else:
                tmp.append(tmp_ch)
        if tmp == []:
            stack.append(3)
        else: #tmp !=[]
            for temp in tmp:
                if not isinstance(temp,int):
                    break
            else:
                stack.append(sum(tmp)*3)
    elif ch ==')':
        while stack!=[]:
            tmp_ch = stack.pop()
            if tmp_ch == '(':
                break
            else:
                tmp.append(tmp_ch)
        if tmp == []:
            stack.append(2)
        else: #tmp !=[]
            for temp in tmp:
                if not isinstance(temp,int):
                    break
            else:
                stack.append(sum(tmp)*2)
    else:
        stack.append(ch)
        
for i in stack:
    if isinstance(i, int):
        result += i
    else:
        result = 0
        break
print(result)

고쳤다. 조건문을 잘못적었더라...

세번째 시도 실패. 세번째 반례: ([)]

반례를 넣으면  ['(', '['] 이상태에서 이렇게 ['['] 괄호가 사라지고 3이 나온다. 

그래서 아예 다른 특수문자로 바꿔버렸다. 그랬더니 해결...

s=input()
stack=[]
result = 0
if s.count('(') != s.count(')') or s.count('[') != s.count(']'):
    s='' 

for ch in s:
    tmp = []
    if ch == ']': 
        while stack!=[]:
            tmp_ch = stack.pop()
            if tmp_ch == '[':
                break
            else:
                tmp.append(tmp_ch)
        if tmp == []:
            stack.append(3)
        else: #tmp !=[]
            for temp in tmp:
                if not isinstance(temp,int):
                    stack.append('_')
                    break
            else:
                stack.append(sum(tmp)*3)
    elif ch ==')':
        while stack!=[]:
            tmp_ch = stack.pop()
            if tmp_ch == '(':
                break
            else:
                tmp.append(tmp_ch)
        if tmp == []:
            stack.append(2)
        else: #tmp !=[]
            for temp in tmp:
                if not isinstance(temp,int):
                    stack.append('_')
                    break
            else:
                stack.append(sum(tmp)*2)
    else:
        stack.append(ch)
for i in stack:
    if isinstance(i, int):
        result += i
    else:
        result = 0
        break
print(result)

 남들은 얼마나 잘짰나 코드확인해봤는데 다 try:except 썼다....

와 이거 때문에 한시간을 날려먹었는데 너무 허탈하다...

 

'STUDY > Algorithm' 카테고리의 다른 글

[백준] 2775 부녀회장이 될테야  (0) 2021.02.07
[백준] 1193 분수찾기  (0) 2021.02.07
[백준] 3985 롤케이크  (0) 2021.02.06
[백준] 2386 도비의 영어공부  (0) 2021.02.06
[백준] 1334 다음 팰린드롬 수  (0) 2021.02.05