[Baekjoon] 1662_압축

Gold V

문제(출처: https://www.acmicpc.net/problem/1662)

---

<압축>

문제 

 

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

 

입력

 

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

 

출력 

 

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 int범위다.

 

 

문제 풀이

   - my solution

import sys

if __name__=='__main__':
    line=sys.stdin.readline().strip()

    result=0 # 길이
    stack=[]
    Qlen=0
    for i in line:
        if i==')': # K(Q) 계산
            temp=0
            while True: # '(' 만날때 까지 반복
                if stack[-1]=='(': # 종료 조건
                    stack.pop()
                    break
                x = stack.pop() # Q 구하기
                if x[-1]=='-':
                    temp+=int(x[:-1]) # 압축 풀어진 길이
                else: # 길이
                    Qlen+=1
            K=stack.pop() # K
            # 문자열이 아닌 압축 푼 길이라는 것을 '-'추가하여 표시
            result=str(int(K)*(Qlen+temp))+'-'
            stack.append(result)
            Qlen=0
        else: # 추가
            stack.append(i)

    answer=0
    for i in stack:
        if i[-1]=='-': # 압축 풀어진 길이
            answer+=int(i[:-1])
        else: # 문자열
            answer+=1
    print(answer)

 

• ')'일 때와 ')'이 아닐 때를 구분하여 구현
• ')'일 때: '('일 때까지 반복 -> 압축 풀어진 길이와 문자열을 구분하여 K(Q) 계산 후 stack 추가
• ')'아닐 때: stack 추가
• answer: stack을 순회하며 압축 풀어진 길이는 그 자체로 더하고 문자열인 것은 1을 더해준다.

압축 풀어진 길이와 문자열을 구분하는 방법)

압축 풀어진 길이는 숫자 뒤에 '-'를 추가하여 stack에 다시 저장해준다.

---

생각🤔

 

압축 푼 길이와 문자열을 구분하는 방법에서 살짝 고민하였다.

열심히 머리를 굴려본 결과 압축 푼 길이라는 것을 알아볼 수 있게 stack에 추가하면서 '-'를 함께

추가해보자는 생각이 들어 위와 같이 구현하였다.

 

 출제자가 이 방법으로 푸는 것을 원하지 않았겠지만.. 이렇게 풀어버렸다..😅

 

---