[백준] 1662번 압축, 파이썬 문제 풀이

문제

백준 1662번 압축된 문자열의 길이를 찾는 문제를 해결했습니다.

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

1662번: 압축

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

입력

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.

예시: 33(562(71(9)))

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.

예시: 19

 

풀이 과정

괄호를 보면 뭔가 스택을 사용해서 풀어야할 것 같은 생각이 듭니다. 실제로 문제를 제출하고 찾아보니 대부분 스택으로 풀었더라구요. 다른 포스팅에서 다뤘던 괄호쌍 맞추기는 스택을 활용해서 풀었지만, 이번 문제는 스택을 활용하지 않았습니다. 자꾸 굳이..? 라는 생각이 들더라구요. 새로운 공간을 차지하는 것도 비효율적으로 느껴졌습니다. 아직 자료구조에 완벽히 적응하지 못했기 때문인 것도 같습니다. 

 

이번 문제는 함수의 재귀 호출을 활용해서 해결했습니다. 여는 괄호 앞에 있는 숫자만 중요하고, 나머지 내용은 의미가 없습니다. 따라서, 0번째 인덱스부터 길이를 체크하고, 괄호가 나오면 괄호 안에 있는 문자열의 길이를 확인합니다. 괄호 안에 또 괄호가 있을 수 있기 때문에, 괄호 안에 있는 문자열의 길이를 구하는 함수를 작성하고, 여는 괄호가 나올 때 마다 함수를 호출했습니다. 함수가 호출되고 나면 인덱스가 조절되어야 하는데, 이 부분에서 살짝 헷갈렸던 것 같습니다. 

 

코드로 확인해보도록 하겠습니다.

def compressed_str_len(compressed_str, idx):
    repeat = int(string[idx-2])
    compression_len = 0
    while(compressed_str[idx] != ')'):
        if (compressed_str[idx] == '('):
            len_res, idx = compressed_str_len(compressed_str, idx+1) #여는 괄호가 나오면 재귀호출
            compression_len += len_res
        else:
            compression_len += 1
            idx+=1
    return repeat*compression_len -1, idx+1 #곱하는 숫자가 두 번 계산되기 때문에 1 뺐음

string = input()
length = 0

j = 0
while(j<len(string)):
    if (string[j] == '('):
        len_res, j = compressed_str_len(string, j+1)
        length += len_res
    elif (string[j] == ')'):
        j+=1
        continue
    else:
        length+=1
        j+=1

print(length)

 

정리

스택으로 구현된 코드를 보면서 저도 한 번 만들어볼까 했는데, 그러지 않기로 했습니다. 제 생각이 짧은 것일 수도 있지만, 스택의 필요성을 못느끼겠습니다. 고집일수도 있지만, 제 코드에 대한 믿음..? 줏대..?라고 생각하겠습니다. 

 

여담으로 처음으로 골드 문제에 도전했는데, 오히려 여지껏 풀었던 문제보다 간단하게 풀었던 것 같습니다. 여태까지 정답 비율을 보면서 쫄았었는데, 이제 정답 비율은 신경쓰지 않기로 했습니다. 인기 문제를 보니 고양이 그림을 출력하는 문제가 33%더라구요.. 다음에는 더 완성도 있는 코드로 작성해보도록 하겠습니다.