[Python] 백준, 2504(스택)

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

2504번: 괄호의 값

백준 저지에 업로드된 스택 문항들을 7개 정도 해결했는데, 이 문항이 가장 어려웠던 것 같다.

인간이 참 대단한게 겨우 괄호를 가지고 이런 문제들을 생각한다는 것도 참 놀랍다.

 

모든 문제가 그렇듯 이 문제 또한 은근히 심플한 풀이를 갖는다.

 

조건문이 남용되는 순간 뭔가 잘못되었음을 본능적으로 직감하게 되는데, 이 문제가 대표적으로 그랬다. 

사고의 부족은 조건문의 남용으로 이어진다. 큰 틀을 짜고 그 안에서 가지를 세워나가는게 역시 좋은 코드가 아닐까싶다.

 

별의 별 생각과 혼란스러움이 가득 들어간 첫번째 풀이.

 

 

# PYTHON CODE (1) 

s = input()
 
answer = []
is_break = False
 
for i in s:
    if len(answer) > 1:
        if type(answer[-1]) == int and type(answer[-2]) == int:
            w = answer.pop()
            e = answer.pop()
            answer.append(w + e)
    if i == '(':
        answer.append('(')
    elif i == '[':
        answer.append('[')
    elif i == ')':
        if len(answer) > 1:
            if type(answer[-1]) == int:
                k = answer.pop()
                answer.pop()
                answer.append(k*2)
            else:
                answer.pop()
                answer.append(2)
        elif answer[0] == '(':
            answer.pop()
            answer.append(2)
        else:
            answer.append('(')
            break
    else:
        if len(answer) > 1:
            if type(answer[-1]) == int:
                j = answer.pop()
                answer.pop()
                answer.append(j*3)
            else:
                answer.pop()
                answer.append(3)
        elif answer[0] == '[':
            answer.pop()
            answer.append(3)
        else:
            answer.append('(')
            break
 
try:
    print(sum(answer))
except TypeError:
    print(0)
 

여전히 기발하다고 생각하는 부분은 정답을 print하는 마지막 4줄이다. 

answer에 숫자들만 남은 case는 올바른 괄호들로 이루어져 있으며, 곱셈 계산을 마쳤기 때문에 단순히 덧셈 계산만 마무리 지어주면 된다. try문을 이용해 괄호를 더해주는 오류가 발생하면 TypeError로 빠져나올 수 있게 설계했다.

 

근데 그 answer까지 오기까지의 과정이 상당히 험난하다. 지금 생각해보니, 우선 곱셈이 마무리된 상태로 answer로 값들이 나올 수가 없다. 예를 들어 괄호로 처음과 끝이 닫혀진 케이스는 마지막 값에 2를 곱해줘야 하므로....

 

try문 또한 별 효율성은 없다. 이 케이스가 올바른 괄호인지를 결정짓는 함수를 하는 만든다면 해결되는 문제더라.

심지어 직전에 풀었던 문제인데 이 문제에서 적용을 시키느냐 못 시키느냐는 오롯이 본인의 역량인가보다.

 

 

 

 

# PYTHON CODE (2) 

s = input()
 
stk1 = []
is_break = False
 
for i in s:
    if i == ')':
        value = 0
        while len(stk1) > 0:
            last = stk1.pop()
            if last == '(':
                if value == 0:
                    stk1.append(2)
                else:
                    stk1.append(2 * value)
                break
            elif last == '[':
                is_break = True
                break
            else:
                value += last
 
    elif i == ']':
        value = 0
        while len(stk1) > 0:
            last = stk1.pop()
            if last == '[':
                if value == 0:
                    stk1.append(3)
                else:
                    stk1.append(3 * value)
                break
            elif last == '(':
                is_break = True
                break
            else:
                value += last
 
    else:
        stk1.append(i)
 
result = 0
 
if is_break == False:
    for i in stk1:
        if i == '(':
            result += i
else:
    print(0)

 

 

 

# PYTHON CODE (3)

s = input()
 
stk1 = []
is_break = False
 
for i in s:
    if i == ')':
        value = 0
        while len(stk1) > 0:
            last = stk1.pop()
            if last == '(':
                if value == 0:
                    stk1.append(2)
                else:
                    stk1.append(2 * value)
                break
            elif last == '[':
                print(0)
                exit(0)
            else:
                value += last
 
    elif i == ']':
        value = 0
        while len(stk1) > 0:
            last = stk1.pop()
            if last == '[':
                if value == 0:
                    stk1.append(3)
                else:
                    stk1.append(3 * value)
                break
            elif last == '(':
                print(0)
                exit(0)
            else:
                value += last
 
    else:
        stk1.append(i)
 
result = 0
 
for i in stk1:
    if i == '(' or i == '[':
        print(0)
        exit(0)
    else:
        result += i
 
print(result)

이건 사실 거의 내 풀이가 아니다. exit함수도 생각도 못했고...

sum과 for문을 통해 답을 도출하는 코드 중에 뭐가 더 빠를까 비교해봤는데, 이외로 for문이 더 속도가 괜찮았다.

 

둘다 O(n) 아닌가? 이 시간 복잡도는 아직도 잘 이해가 안간다. 다시 공부해봐야할듯.

 

이대로 끝내기가 아쉬워서 복습도 할겸 두 함수를 이용한 코드도 작성해봤다. 나름 술술 써지는 걸 보면 그래도 어느 정도는 확실히 이해한 것 같다.

 

 

 

 

 

# PYTHON CODE (4)

def stack_check(seq):
    stk = []
    for i in seq:
        if i == '(' or i == '[':
            stk.append(i)
        elif i == ')':
            if stk:
                if stk[-1] == '(':
                    stk.pop()
                else: return False
            else:
                return False
        else:
            if stk:
                if stk[-1] == '[':
                    stk.pop()
                else: return False
            else:
                return False
    return False if stk else True
 
def stack_calcu(seq):
    stk = []
    for i in seq:
        if i == '(' or i == '[':
            stk.append(i)
        elif i == ')':
            value = 0
            while stk:
                if stk[-1] == '(':
                    if value == 0:
                        stk[-1] = 2
                    else:
                        stk[-1] = value * 2
                    break
                else:
                    value += stk.pop()
        else:
            value = 0
            while stk:
                if stk[-1] == '[':
                    if value == 0:
                        stk[-1] = 3
                    else:
                        stk[-1] = value * 3
                    break
                else:
                    value += stk.pop()
    return stk
 
result = 0
answer = input()
 
if stack_check(answer) == False:
    print(0)
else:
    for i in stack_calcu(answer):
        result += i
    print(result)

설명은 생략.