백준 - 2504번(스택,구현,문자열)

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

2504번: 괄호의 값

실버 1 구현 문제 중에 정답률이 압도적으로 낮아서 한번 풀어봤다.

이 문제가 어려운건 처음 해당 문제를 어느 관점에서 접근하냐가 어려운 것이다.

이 문제를 처음 접한 상태에서 읽자마자 이걸 두 개의 스택을 이용해서 풀면 시간 초과를 안 낼 수 있겠다..!라고 생각하는 것이 쉽지 않다.

시간 초과, 각종 에러로 여러 번 만에 성공했다.. 역시 구현 문제는 시간도 오래 걸리고 어렵다..

 

import sys

arr = sys.stdin.readline().rstrip()
arr.replace('()','2')
arr.replace('[]','3')
arr = list(arr)

q = 0
w = 0
e = 0
r = 0
#짝이 안맞는게 존재하는 경우 확실하게 잘못된 입력임을 알 수 있다.
for i in range(len(arr)):
    if arr[i] == '(':
        q = q + 1
    elif arr[i] == ')':
        w = w + 1
    elif arr[i] == '[':
        e = e+1
    elif arr[i] == ']':
        r = r + 1
if q != w or e != r:
    print(0)
    exit(0)

tmp = []
tmp.append(arr.pop())

while arr:
    x = arr.pop()
    k = 0
    if x == '(':
        while tmp:
            if tmp[-1].isdigit():
                t = tmp.pop()
                k = k + int(t)
            else:
                a = tmp.pop()
                if k != 0:
                    tmp.append(str(k*2))
                elif k == 0 and a == ')':
                    tmp.append(str(2))
                else:
                    tmp.append(str(a))
                break

    elif x == '[':
        while 1:
            if tmp[-1].isdigit():
                t = tmp.pop()
                k = k + int(t)
            else:
                a = tmp.pop()
                if k != 0:
                    tmp.append(str(k*3))
                elif k == 0 and a == ']':
                    tmp.append(str(3))
                else:
                    tmp.append(str(a))
                break
    else:
        tmp.append(x)

ans = 0
for i in tmp:
    if i.isdigit():
        ans = ans + int(i)
    else:
        print(0)
        exit(0)

print(ans)

해당 코드를 보면 arr은 처음에 입력받는 배열 tmp는 arr 스택에서 pop 된 값들을 append 해주는 배열이다.

즉 tmp는 arr을 뒤에서부터 보는 배열이라고 할 수 있다.

 

먼저 (,) or [,] 짝이 안 맞는 경우 프로그램을 실행해 볼 필요도 없이 잘못된 입력이란 걸 생각할 수 있다.

이렇게 한 단계의 필터링을 거치고 나면 원리는 다음과 같다.

x = arr.pop() 일 때 x가 ( 이거나 [라는 의미는 반드시 앞에 ) 혹은 ]가 존재한다는 것이다.

따라서 tmp 배열 안에서 ( 일 때는 ) [ 일때는 ]를 만날 때까지 반복문으로 찾아준다.

이때 정수가 있으면 값을 더해줘야 하기 때문에 정수 판별을 위해 isdigit 함수를 사용해준다.

정수가 존재하면 k*2 or k*3을 해주고 그렇지 않을 경우 2 or 3을 넣어 준다.

만약에 본인의 짝 말고 다른 기호가 앞에 있으면 tmp에 다시 넣어준다.

이를 반복하면 tmp 배열에는 숫자만 남는다.

해당 숫자들을 모두 더해주면 값을 출력할 수 있다.