[알고리즘] 백준 1662 Python

 

분류

스택, 재귀

혼자 힘으로 해결 했는가?

△ (예외를 못 잡아서 오래걸림)

느낀 점

스택을 사용하는 문제이나 구현력이 조금 필요한 문제라고 생각한다.

 

처음에는 재귀로 접근을 했으나 

 

2(1)3(12(2)) 와 같이 완전한 괄호 쌍이 여러개가 나오는 경우를 놓쳤고, 이런 경우까지 해결하기에는 스택을 사용해야

해결이 가능 할 것 같았다.

 

이를 위해 스택에 앞 부분부터 집어넣고 )를 만난 경우 스택에서 값을 빼서 계산하는 방식으로 구현을 했으나

 

한가지 발목은  잡은 부분이

 

이 문제는 딱 봐도 문자열을 직접 만들면서 진행하면 시간초과 or 메모리 초과가 무조건 생길 문제이다.

즉, 나는 중간 값으로 문자열 자체를 활용하면 안되고 길이만을 저장해야 하는데,

 

562(12(2))와 같은 경우, 스택에 5 6 2 이런 문자열에 대한 정보가 아닌 길이값인 '3' 이런 형태만 저장 할 경우

 

() 내부 값을 계산 할 때, 올바르게 계산이 되지 않는다.

 

따라서 이를 어떻게 해결할지가 가장 고민이었고 그냥 스택에 문자, 숫자(길이) 를 모두 저장하고

 

스택에서 빼낸 타입에 따라서 처리하는 방식을 힘겹게 고안했다.

 

이 문제에서 내 발목을 잡은 부분은 문자열, 숫자 이 두가지 타입을 모두 사용하되 Python의 type 함수를 사용하는 것을

생각하지 못해서인듯 싶다.

 

위의 발상을 하기 전에 스택에 반대로 집어넣는 코드를 작성 중이었기 때문에 최종 코드는 스택에 거꾸로 집어 넣는다.

 

---

 

내가 작성한 코드

S = input()

stack = []
N = len(S)

for i in range(N - 1, -1, -1):
    stack.append(S[i])
    if i == N - 1:
        continue
    if S[i + 1] == "(":
        s = 0
        stack.pop()
        stack.pop()
        while stack:
            n = stack.pop()
            if n == ")":
                break
            else:
                if type(n) == str:
                    s += 1
                else:
                    s += n
        stack.append(s * int(S[i]))

ans = 0
while stack:
    n = stack.pop()
    if type(n) == int:
        ans += n
    else:
        ans += 1

print(ans)

 

 

 

---

비슷한 문제들