[프로그래머스] 문자열 압축 (문제 설명, 해결 과정, 코드 전문, C++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

본 문제는 프로그래머스의  문자열 압축 문제있습다.

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

 

 

 

 

해결 과정

 

주어진 문자열 s를 가능한 모든 경우로 나눠 문자열 2차원 문자열 벡터에 넣습니다.

이후 스택에 각 차원마다 중복 등을 감안하여 문자열의 길이를 구하고 각 차원마다 구해진 문자열 길이들 중 

최소값을 반환합니다.

가능한 모든 경우로 문자열을 나눌때 기준의 길이가 전체 문자열의 절반을 초과할 수 없기에

s.size()/2 동안 반복한다. 1의 경우에는 예외적으로 반환합니다.

 

 

 

코드 전문

 

 

#include <string>
#include <vector>
#include <stack>
#include <algorithm>


using namespace std;

int solution(string s) { 
    int answer = 0;
    vector<vector<string>> sliced_s_vec(s.size() / 2);  
    string temp_str{};
    stack<string> stk;
    vector<int> sliced_s_lengs;

    
    if (s.size() == 1) return 1;
    // slicing depending on string length, i == string length to slice
    for (int i=1; i <= s.size() / 2; i++)
    {
        for (int j=0; j < s.size(); j++)
        {
            temp_str += s[j];
            if (temp_str.size() == i || j == s.size()-1)
            {
                sliced_s_vec[i-1].push_back(temp_str);
                temp_str = "";
            }
        }
    }


    for (int i=0; i < sliced_s_vec.size(); i++)
    {
        while (!stk.empty()) stk.pop();
        int overlap_cnt = 0;
        int temp_sum = 0;
        
        for (int j=0; j < sliced_s_vec[i].size(); j++)
        {
            if (!stk.empty() && sliced_s_vec[i][j] == stk.top())
            {
                stk.push(sliced_s_vec[i][j]);
                if (overlap_cnt == 1 || overlap_cnt == 9 ||
                    overlap_cnt == 99 || overlap_cnt == 999) { temp_sum += 1; }
                overlap_cnt++;
                
                stk.top();
            }
            else
            {
                stk.push(sliced_s_vec[i][j]);
                overlap_cnt = 1;
                temp_sum += sliced_s_vec[i][j].size();
            }
            

        }
        sliced_s_lengs.push_back(temp_sum);
    }

    answer =  *min_element(sliced_s_lengs.begin(), sliced_s_lengs.end());

    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

code dump의 뿌리를 슬슬 끊을 때가 된 것 같다. 배열에 인덱스를 통하여 접근 시 해당 인덱스에 메모리가 할당되어야한다. 초기화 구문에 vec(10); 같이 미리 최소한의 메모리를 둔다던가 하며, 테스트 케이스 작성 시 극단적인 예나 일반적인 예를 염두하는 것이 좋아 보인다. 문자열을 다루며 스택을 자주 사용했는데 필히 나의 잘못이겠지만

투포인터를 쓸 때 보다 가독성이 낮아지는 것 같다.  스택 다룰 시 조건문에 empty 여부를 같이 사용하면 따로 스택의 top 값과 비교 시 push의 콜 타이밍을 맞출 수 있다. 다차원 배열 반복 시 스택을 공용한다면 초기화는 꼭 해주자.

algorithm 라이브버리의 min_element(iter_from, iter_to) 잘 썼습니다. 반환값은 반복자이군요

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.