엘리스 코드 챌린지 예선 [Day 3] 문제풀이

문제

목표량

• 시간 제한: 1초

엘리스 토끼는 문자열을 직접 압축 해제하려고 합니다.

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열 중 어떤 부분 문자열은 K(Q)와 같이 압축할 수 있습니다. 이것은 Q라는 문자열이 K 번 반복된다는 뜻입니다. K는 한 자릿수의 정수이고, Q는 0자리 이상의 문자열입니다.

예를 들면, 53(8)은 다음과 같이 압축을 해제할 수 있습니다.

53(8) = 5 + 3(8) = 5 + 888 = 5888

압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하세요.

지시사항

입력

• 첫째 줄에 압축된 문자열 S를 입력합니다.
• S의 길이는 최대 50입니다.
• 문자열은 (, ), 숫자로만 구성되어 있습니다.

출력

• 압축되지 않은 문자열의 길이를 출력합니다.

입력 예시

11(18(72(7)))

출력 예시

26

풀이

접근

이번 문제는 예외 상황을 고려해야 한다.

나올 수 있는 테스트 케이스를 생각해 보면 

1. 정상적으로 압축되어 있는 수들의 집합 ex) 53(8) = 5 + 3(8) = 5 + 888 = 5888(정답은 4)
2. 괄호 없이 수만 나오는 경우 ex) 1111 = 1111(정답은 4)
3. Q가 0자리 이상이므로 괄호 안에 아무것도 없는 상황 ex) 5() = 0(정답은 0)

이번 문제에서 입력을 받는 과정을 많이 고민했다.

가장 먼저 생각한 방법은

숫자만 push 후 pop해서 계산을 진행하는 방법이었는데, 테스트 케이스 2, 3번을 예외 처리하는 과정이 너무 복잡해서 구현하다 포기했다.

 

두 번째 방법은

문자열로 입력받아 하나씩 처리하는 방법이다. 

뒤에서부터 확인하는 과정을 진행하고, 여는 괄호가 나올 때마다 계산을 진행하는 방식으로 구현하였다.  

풀이

1. 문자열을 입력받는다
2. 뒤에서부터 숫자이면 Qn을 증가시킨다.
3. 여는 괄호가 나오면 바로 앞 숫자와 Qn을 곱한다.
4. 3번에서 사용한 숫자 앞의 숫자들은 더해야 하므로 다시 닫는 괄호가 나올 때까지 자릿수를 계산해 준다(Kn)
5. Kn과 3번에서 구한 수를 더해준다.
6. 3~5번 과정을 반복해 준다. 

코드

#include <iostream>
#include <string>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int i, Qn, Kn;
	int result = 0;
	string S;
	cin >> S;
	
	i = S.size() - 1;
	Qn = Kn = 0;
	while (i >= 0)
	{
		if (isdigit(S[i]))
		{
			Qn++;
			i--;
		}
		else if (S[i] == '(' && isdigit(S[i - 1]))
		{
			result = (S[i - 1] - '0') * Qn;
			i -= 2;
			while (i >= 0 && isdigit(S[i]))
			{
				Kn++;
				i--;
			}
			result += Kn;
			
			Kn = 0;
			Qn = result;
		}
		else if (S[i] == ')')
		{
			i--;
		}
	}
	if (Qn != result)
		result += Qn;

	cout << result;



	return 0;
}

↑ 더 보기 클릭으로 펼치기

 

모범답안

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    string input;
    cin >> input;

    vector<char> stack;
    vector<int> depth_result(50, 0);
    int depth = 0;

    for (char ch : input) {
        if (ch != ')') {
            if (ch == '(') {
                depth++;
                depth_result[depth] = 0;
            }
            stack.push_back(ch);
        } else {
            for (int i = stack.size() - 1; i >= 0; --i) {
                if (stack[i] == '(') {
                    int num = depth_result[depth];
                    for (int j = i + 1; j < stack.size(); ++j) {
                        num += 1;
                    }
                    depth--;
                    depth_result[depth] += num * (stack[i - 1] - '0');
                    stack.erase(stack.begin() + i - 1, stack.end());
                    break;
                }
            }
        }
    }
    cout << depth_result[0] + stack.size() << endl;

    return 0;
}

↑ 더 보기 클릭으로 펼치기

 

후기

문자열 다루는 기술이 많이 부족한 것 같다. 

시간을 생각보다 너무 많이 써버려서 놀랐다.