백준 1662 압축

문제링크 : https://www.acmicpc.net/problem/1662

아이디어

• 스택을 사용하여 (을 사용하면 나오는 위치를 우선 구해놓자
  • 재귀함수를 사용해서 (만나면 앞에 숫자에서 곱하기 사용

시간복잡도 계산

• 스택사용해서 괄호 시작 및 끝나는 위치 매핑 : O(S)
  • 재귀함수 중 순회 : O(S)
• 총합 : O(S)

자료구조

• 괄호 시작 및 끝나는 위치 계산용 스택 : stack(int)
  • 스택안에 들어가는 값 : 각각 문자열 인덱스
  • 최대값 : 50 > INT 가능
    • 괄호 시작 및 끝나는 위치 기록 : map[60]
  • 들어가는 값 : 문자열 인덱스
  • 최대값 : 50 > INT 가능
    • 압축안된 문자열 길이 rs
  • 한번 괄호 쌍에 필요한 문자열 최소 3개
  • 그럼 최대 50/3 = 17번이 곱해질수 있음
  • 최대 9^17 > long long 사용

코드(C++)

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
typedef long long ll;
 
int map[60];
string s;
 
ll recur(int st, int en) {
    ll rs=0;
    for(int i=st; i<=en; i++) {
        
        // 만약 괄호 만나면 해당 괄호 끝에 해당하는 부분까지 곱해주기
        if(s[i] == '(') {
            // 이전글자 빼주기
            rs--;
            ll preChar = s[i-1]-'0';
            rs += preChar * recur(i+1,map[i]-1);
            // 괄호로 인덱스 이동
            i = map[i];
        } else {
            rs++;
        }
    }
    
    return rs;
}
 
int main() {
    fill(map, map+60, 0);
    
    cin >> s;
    stack<char> st;
    
    // 괄호 끝나는 위치 기록함
    for(int i=0; i<s.size(); i++) {
        char ec = s[i];
        if(ec == '(') {
            st.push(i);
        } else if(ec==')') {
            int ei = st.top(); st.pop();
            // 괄호 끝나는 위치 기록
            map[ei] = i;
        }
    }
    
    cout << recur(0, s.size()-1) << '\n';
    
    return 0;
}
 

문제유형

• 시뮬레이션 - 스택 압축
  • 괄호 통해서 압축하는문제
  • 사전에 스택으로, 각각 괄호에서 끝나는 부분 구해놓은 뒤
  • 재귀함수 통해서 괄호 나올때마다 계산해주는 문제