[백준 알고리즘] 1662번 압축

문제

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

풀이

예제입력이 3 3 ( 5 6 2 ( 7 1 ( 9 ) ) ) 인데 출력은 압축되지 않은 문자열의 길이이다

압축을 하나씩 풀어보면

3 3 ( 5 6 2 ( 7 1 9 ) ) 

3 3 ( 5 6 2 7 1 9 7 1 9 ) 

3 3 5 6 2 7 1 9 7 1 9 5 6 2 7 1 9 7 1 9 5 6 2 7 1 9 7 1 9

... 라고 생각해서 답이 29라 생각했는데 예제답이 19여서 어제 하루종일 문제이해를 못했다 바보같이 반복횟수를 나타내는 K도 같이 반복해버렸다

다시 압축을 풀어보면

3 3 ( 5 6 2 ( 7 1 ( 9 ) ) ) 

3 3 ( 5 6 2 ( 7 9 ) ) 

3 3 ( 5 6 7 9 7 9 ) 

3 5 6 7 9 7 9 5 6 7 9 7 9 5 6 7 9 7 9

이라서 압축을 푼 문자열의 길이는 19가 맞다. char배열을 뒤에서 부터 읽으면서 )가 발견되면 함 수를 호출해서 괄호안의 숫자를 센다 그리고 (가 발견되면 값을 return하고 그 앞의 숫자와 리턴값을 곱하고 계속해서 더해간다.

+추가 2018.9.21 

char 배열을 읽을 때 뒤에서 부터 읽어야하는데 가장 앞에 있는 )부터 찾아야 한다! 아니다 뭘 먼저 찾아서 계산을 시작하는게 나을까.. 제일 뒤에 있는 (를 찾아서 )가 되면 종료하고 또 다시 (를 찾고.. 하는 방법으로 접근을 해보겠다!

+추가 2018.11.07

드디어 이 문제에서 탈출! 아마 이 블로그 처음 만들었을 때 도전했던 문제였던 걸로 기억한다. 9월 21일에 다시 풀어야지 하고 안풀었었나.. 다시 오늘 푸는데 생각보다 시간이 많이 걸렸다. 처음 문제를 풀 때는 당연히 처음 ( 만 생각했었는데 오늘은 그래도 금방 ) 를 먼저 찾고 그 안에서 계속 재귀호출을 해야겠다는 생각을 했다. 처음에는 재귀 안에서 센 숫자개수만큼 return 을 해줘야지 생각했더니 돌아왔을 때 시작해야하는 좌표가 엉켜버렸고, 그렇다고 센 숫자를 전역변수로 두고 시작해야하는 좌표를 return 하니 카운트가 엉망이 되어버렸다. 너무 복잡하게 돌아서 풀고 있는 것 같다는 생각이 들었고 pair<int, int> 로 결과값을 둘 다 return 해주도록 하니 금방 해결됐다. 제일 뒤에서부터 카운트를 세다가 )가 발견되면 그 안에 카운트를 센다음에 return 을 하고 반환값을 받을 때는 이어서 시작할 수 있는 좌표로 바꿔주고 이어서 시작하는 자리에 압축시킨 수가 있으니 반환값과 압축시킨 수를 곱해주도록 해서 계속해서 카운트를 늘려갔다.

코드

#include<iostream>

#include<string.h>

using namespace std;

pair<int, int> recur(char input[], int curr){

int cnt=0;

int i;

for(i=curr; i >=0 ; i--){

if(input[i] == '('){

break;

}

else if(input[i] == ')'){

pair<int, int> result = recur(input, i-1); //괄호 안에 있는 갯수

i= result.first;

cnt += (input[i]-'0')*(result.second);

}

else{

cnt++;

}

}

return make_pair(i-1, cnt);

}

int main()

{

char input[50];

cin>>input;

cout<<recur(input, strlen(input)-1).second<<endl;

return 0;

}