백준 1662 압축 [C++]

작성일 | In |

Problem : 압축

유형 : 스택

문제 해석

  • 압축된 문자열 S 의 압축전 길이를 구하라.
  • 숫자가 있어서 헷갈렸던 문제이다
  • 12(345) 가 있다면
    • 345 를 2번 반복해야 한다.
    • 345 를 12번 반복 하는 것이 아니다!
    • 결과 : 1345345

해결 전략

  • 스택 을 이용하여 해결했다.
  • 스택의 괄호쌍 응용 문제이다.
  • 닫히는 괄호가 나올때, 여는 괄호가 나올떄 까지의 문자열의 길이에 관심을 가진다.
    • 여는 괄호 바로 앞 한자리 숫자 에 지금까지 구한 문자열의 길이를 곱해준다.

구현

  • 스택에 정보를 두가지를 보관했다.
  • { 문자, 길이 }
  • 처음 스택에 들어갈때의 길이는 1로 넣어준다.
  • 3(45) 의 경우, ` {3, len = 1} ( {4, len = 1} ,{5, len = 1} ) `가 들어가있다.
  • 스택에서 여는 괄호를 찾을때 까지 pop을 하며, 스택에 있던 len 을 더해준다. (1+1)
  • 여는 괄호를 찾은 경우, {3, len 1} 의 len에 3 * pop한 len의 합 (2)을 넣어준다.
  • 모든 과정이 끝난뒤, 스택에 있는 len 의 합을 전부 구한다. (6)

주의할 점

  • 12(34) 의 경우 13434 가 되므로, 앞의 1도 같이 세주어야 한다.

코드

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
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define pci pair<char,int>

using namespace std;

string zipString;

void solve() {
    cin >> zipString;
    stack<pci> s;
    int strSize = 0;

    for (char c : zipString) {
        if (c == ')') {
            while (1) {
                if (s.top().first == '(') {
                    s.pop();
                    int repeatCount = s.top().first - '0';
                    s.top().second = repeatCount * strSize;
                    strSize = 0;
                    break;
                }
                strSize += s.top().second;
                s.pop();
            }
        }
        else s.push({ c, 1 });
    }
    int answer = 0;
    while (!s.empty()) {
        answer += s.top().second;
        s.pop();
    }
    cout << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 닫는 괄호는 스택에 넣지도 않았는데 넣었다고 착각했었다.
  • 다른분들 코드를보니 재귀 로 해결하신 솔루션이 많다. 나중에 재귀로도 다시 풀어볼까 한다. 11-03 작성