Algorithm/Data Structure
(Python) - BOJ(1662번) : 압축
하눤석
2022. 1. 27. 09:29
728x90
https://www.acmicpc.net/problem/1662
1662번: 압축
압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이
www.acmicpc.net
- 해설 :
숫자들로 이루어진 문자열 S가 주어질 때 K(Q) 라는 구조는 Q가 K번 반복된다는 의미이다.
이를 통해 원래 숫자들로 이루어진 문자열의 길이를 찾는 문제이다.
- 풀이 :
Queue를 이용하여 (를 만났을 때, )를 만나기 전까지 숫자들을 합치고 이를 ( 앞의 숫자만큼 곱하여 원래 문자열로 더해주었다.
- 소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
from collections import deque
if __name__ == "__main__":
string = input() # 압축되지 않은 문자열의 길이 출력
q = deque()
for i in range(len(string)):
if string[i] != ")":
if string[i] == "(":
q.append(string[i])
else:
q.append(int(string[i])) # 숫자 형태로 반환하여 삽입
else: # ")" 기호가 나온 상황
# "(" 기호를 만날 때까지 숫자의 개수를 센다
length = 0
while q:
value = q.pop()
if value == "(":
break
else:
if value >= 10:
length += value - 10
else:
length += 1
length = length * q[-1] + 10
q.pop() # 마지막 숫자 제거
q.append(length)
answer = 0
for i in range(len(q)):
if q[i] >= 10:
answer += q[i] - 10
else:
answer += 1
print(answer)
|
cs |
320x100