[level 2] 카카오2020 문자열 압축 , substr

https://programmers.co.kr/learn/courses/30/lessons/60057

 

 

첫 번째 풀이

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

using namespace std;

int solution(string s) {
    int answer = s.length();
    stack <string> stack1;
    stack <int> stack2;
    string unit;
    int cnt=0;
    for(int i = 1 ; i < s.length()/2+1 ;i++){
        for(int j = 0; j<s.length();j+=i){ 
          
            if(stack1.empty()){
                stack1.push(s.substr(j,i));
                stack2.push(1);
                continue;
            }
            
            unit = stack1.top();
          
            if(unit.compare(s.substr(j,i)) == 0){
                cnt = stack2.top()+1;
                stack2.pop();
                stack2.push(cnt);
            }
            else{
                stack1.push(s.substr(j,i));
                stack2.push(1);
            }
            
        }
        cnt = 0;
        while(!stack1.empty()){
            cnt += (stack1.top()).length();
            if(stack2.top() != 1) 
                cnt +=(  to_string(stack2.top()) ).length();
            stack1.pop();
            stack2.pop();
        }   
        if(cnt < answer)
            answer= cnt;
        
    }
    
    return answer;
}

stack1 : 문자열 유닛을 담는 스택

stack2 : 문자열 횟수를 넣는 스택

stack1의 맨 위 요소와 문자열 유닛을 비교해 같으면 stack2 맨 위 값을 +1 해준다.

 

배운 내용

• str(위치, 개수) : string의 서부 sub tring
• to_string 
  • 헤더 파일 : string