[백준 01662] 압축 [Java]

문제

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

입력

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

출력

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

---

풀이

문자열 압축 문제이기 때문에, 문제에서 주어진 압축해제 방식으로 가장 안쪽 압축부터 풀어주면 된다.

때문에 가장 안쪽 압축이 나올 때 까지 stack에 push만 해주며 패스하자.

 

가장 안쪽의 압축 문자열에 대해 압축의 끝을 의미하는 ' ) '가 나왔다면, 다시 stack으로부터 압축의 시작인 ' ( ' 을 찾아주자. 만약 ' | ' 가 아닌 경우에만 Q의 길이를 1씩 더하고, 문제에서 주어진 압축 해제로 만들어지는 문자열의 길이 ( K * lenQ )를 stack에 다시 넣어주자.

  

위에서 단순히 한 개의 문자가 아닌, 압축해제에 따른 숫자의 길이를 문자열로 넣어주었다.

해당 문자열이 한 개의 숫자를 의미하는게 아닌, 숫자의 자릿수를 의미하는 문자열임을 표시할 필요가 있다.

때문에 ' | ' 를 넣어주었다.

즉, ' | ' 문자 다음으로 pop을 해서 뽑아낸 숫자는, 하나의 문자가 아닌, 숫자의 자릿수이다. 그렇기 때문에 위에서 pop한 문자가 ' | '인 경우에는 다음 수를 뽑아 정수로 변환하고, 그만큼 Q의 길이( lenQ )를 증가시킨 것이다. 주어진 문자열 S에 대해 위의 탐색 과정이 끝났다면, stack에는 하나의 문자 또는 숫자의 자릿수들이 존재한다. 

 

위와 동일한 방법으로 압축 해제한 문자열의 길이를 계산해주자.

---

풀이 추가

문제를 Stack 분류로 찾으며 풀다보니 풀면서도 Recursive와 유사한 문제들이 몇개 보였다.

이 문제 또한 Recursive로 풀이가 가능하며 더욱 직관적이다. 

 

위에서 압축의 시작과 끝인 ' ( ', ' ) '을 찾으며 Stack에서 pop, push해주었다. 이 구간에 대해 Recursive를 적용해보자.

단, Recursive의 특성 상 아래단에서 탐색한 범위에 대해 중복으로 탐색할 수 있다. 때문에 boolean배열을 사용하든 위의 방법대로 " _ "등의 문자열을 넣어 이미 탐색한 범위임을 표시해주자.

---

소스코드

보기

---

출처

1662번: 압축