[Java] BOJ1662, 백준 - 압축

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

1662번: 압축

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128MB	3776	1120	898	33.495%

문제

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

 

입력

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

 

출력

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

 

<풀이>

사실 처음에 문제를 읽었을 때 문제의 매커니즘을 이해하기 힘들었다ㅠ 질문 보고 알았음

그러니 문제에 대한 내용부터 짚고 넘어가도록 하자.

 

괄호가 있을 때, 그 문자열은 압축된 형태이다.

K(Q)와 같은 형태로 되어있는데, 이 의미는 Q라는 문자열이 K번 반복된다는 뜻이다.

우리가 알아야 할 것은 압축이 풀렸을 때 원본 문자열의 '길이'를 구하는 것이다.

예제를 통해 알아보도록 하자. 가장 안쪽에 압축된 부분부터 보자

• 33(562(71(9)))

1(9)가 의미하는 바는 9라는 문자열이 한 번 반복된다는 뜻이다.

1(9)의 압축을 풀면 다음과 같이 된다.

• 33(562(79))

2(79)의 의미는 79라는 문자열이 두 번 반복된다는 뜻이다.

2(79)의 압축을 풀면 다음과 같이 된다.

33(567979)

> 3567979567979567979567979 해서 18자리가 나오는 것

 

다른 예시로 예를 들어보면

74(3(5(1)))1 > 74(3(11111))1 > 74(111111111111111)1 > 71111.....    ....1 = 61자리의 문지열이 나오게 된다.

 

여기서 문제를 풀 때 짚고 넘어가야 할 점들이 생긴다.

1. 이중,, 삼중,,, N중으로 압축이 되어있을 경우 가장 안쪽의 압축된 것부터 풀어줘야 한다는 것이다.

(압축을 풀 때 문자열의 길이가 중첩되기 때문)

2. 문자열의 길이만 알면 되기 때문에, 문자열이 정확히 무엇인지는 굳이 알 필요가 없다.

 

그렇기  때문에 함수를 이용하여 괄호 내의 문자열 길이=K(Q) 를 넘겨주는 방식으로 문제를 해결해보도록 하겠다.다만, 문자열의 맨 앞부터 검사할 경우 괄호가 나왔을 때 포인터를 하나 감소시켜 괄호 앞의 수를 저장해놔야 하는 점이 번거로울 것 같아서 문자열의 맨 뒤부터 검사하였다.그러면 )가 나오면 괄호가 시작되는것이고, (가 나오면 괄호가 끝나는것이 되는데, (가 나와 괄호가 끝났을 경우 바로 직전의 숫자와 곱해주면 되기 때문에 포인터를 << 방향으로만 계속 움직여줄 수 있음

 

1. 괄호가 나왔을 경우
   1. 괄호가 닫히면(=(가 나오면) K(Q)의 길이를 리턴해준다.
   2. 괄호 안에 또 괄호가 있을 경우(=N중으로 압축된 경우, )가 나오는 경우) 내부 압축부터 먼저 풀어서 괄호 안의 문자열 길이에 더해준다.
   3. 괄호가 닫힐때까지 2번을 실행한다.
2. 숫자가 나왔을 경우
   1. 문자열의 길이를 1만큼 늘려준다.

 

시간복잡도/메모리

함수를 N중으로 실행하는 경우가 생기기는 하지만, 사실상 static으로 선언된 포인터가 한 방향으로 쭉 이동하기 때문에 문자열의 길이 만큼만 실행된다. 최대 문자열의 길이는 50이기때문에 OK

메모리 또한 특별히 고려할 수준은 아니다.

 

소스코드

import java.io.*;

public class Main {

	private static String s;
	private static int p;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tot_length = 0;
		s = br.readLine();
		// 문자열의 맨 끝에 포인터를 둔다.
		p = s.length() - 1;

		while (p >= 0) {
			if (s.charAt(p) == ')') {
				// 괄호가 있다면 괄호 내의 문자열 길이를 계산합니다.
				tot_length += go();
			} else { // 괄호가 없다면 그냥 길이에 1을 더합니다.
				tot_length++;
			}
			// 커서를 뒤에서 앞으로 한 칸씩 이동하며 탐색합니다.
			p--;
		}
		System.out.println(tot_length);
	}

	// 괄호가 열렸을 때 괄호 내의 문자열 길이를 측정할 함수
	// 괄호 앞의 숫자까지 곱한 값을 return 해줍니다.
	private static int go() {
		int curr_length = 0;

		while (p >= 0) {
			if (s.charAt(p) == '(') {
				curr_length *= (s.charAt(--p) - '0');
				break;
			} else if (s.charAt(p--) == ')') {
				// 또다른 괄호가 있다면 현재 길이에 괄호 안의 길이를 더해준다.
				curr_length += go();
			} else {
				// 괄호가 없다면 그냥 길이에 1을 더해준다.
				curr_length++;
			}
		}

		// 현재 커서 위치를 처리했으니 커서를 한 칸 앞으로 당긴다.
		p--;
		// 괄호 안에 있는 문자열의 길이들을 return해주면 완료
		return curr_length;
	}
}

대부분 스택을 이용하여 풀었던데, 스택을 이용하여 푸는 방법으로도 한 번 풀어봐야겠다.