백준 BOJ 1662 - 압축

파이썬 스터디용으로 풀었던 문제.

파이썬어려워요 흑흑

 

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

1662번: 압축

처음에는 입력값을 그대로 스택에 넣고 괄호쌍을 만날때 되돌아가는 방식으로

정답을 구했는데,

 

반례로 123(12)123(12) 와 같이 괄호쌍 두개가 떨어져있는 경우에는 제대로 계산을 못한다.

val = input()
st = []

ans = 0

for i in val :
    if i != ')' :
        st.append(i)
    else :
        while st[-1] != '(' :
            st.pop()
            ans += 1
        st.pop()
        time = int(st.pop())
        ans *= time

while len(st) != 0 :
    st.pop()
    ans += 1

print(ans)

오답 소스코드에서 123(12)123(12) 를 입력으로 넣어주면

앞선 123(12)에서 계산했던 값이 뒷 입력 123(12)에 영향을 주어서

28이라는 오답을 출력한다.

실제 정답은 16.

 

그래서 스택에 부분 문자열의 길이를 저장하도록 했다.

 

입력 : 1 2 3(12) 1 2 3(12)

스택 : 1 1 6 1 1 6 -> 16

 

소스코드 펼쳐보기

s = input()
st = []

for i in range(len(s)) :
    if s[i] == '(' :
        st.pop()
        st.append(int(s[i-1]))
        st.append(s[i])

    elif s[i] == ')' :
        time = 0
        while True :
            tmp = st.pop()
            if tmp == '(' :
                break
            time += tmp
        st.append(time * int(st.pop()))

    else :
        st.append(1)

ans = 0
for i in st :
    ans += i

print(ans)

반례를 찾기 전까지는 맞왜틀이라고 생각하고 있었어서

뇌절이 좀 있었던 문제