본문 바로가기
CS/알고리즘

프로그래머스 - 문자열 압축

by zieunee 2021. 4. 12.
반응형

programmers.co.kr/learn/courses/30/lessons/60057?language=cpp

 

코딩테스트 연습 - 문자열 압축

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문

programmers.co.kr

은근 오래걸렸다 .. 2시간? 

 

2,3개씩 비교할때 문자열 전체크기보다 넘을때의 경우를 생각하느라 오래걸림 

 

문자열이 총 10개인데 3/3/3/1이렇게 비교해야함 이럴경우 

  if (a >= s.size()) {
    newStr = savedStr + selectedStr;
    flag = 1;
    break;
  }

이렇게 처리함 

원래 저기에서 바로 newStr에 더해줬더니 ..

newStr += cnt == 1 ? savedStr : to_string(cnt) + savedStr; // s.size()넘었을 경우 남은 str맨뒤에 추가 해줘야한다. 

이부분에서도 더해지고 위에서도 더해져서 문제가 생겼음  > 그래서 savedStr로 넣어주고 for문 밖에서 처리되게 수정!

 

다양한 경우의 수를 생각해야한다.

 

사이즈가 10일때

2/2/2/2/2

3/3/3/1

5/5

딱 떨어지는 경우, 배열밖으로 나가는 경우 등등

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(string s) {
    int answer = 0;
    int minSize = 987654321;
    for (int i = 1; i <= s.size(); i++) {
        string savedStr;
        string newStr;
        int cnt = 0;
        int start = 0;
        int flag = 0;
        for (int a = 0; a < i; a++) {
            savedStr += s[a];
        }
        for (int j = 0; j < s.size(); j += i) {
            string selectedStr;
            for (int a = j; a < j + i; a++) {
                if (a >= s.size()) {
                    savedStr = savedStr + selectedStr;
                    flag = 1;
                    break;
                }
                selectedStr += s[a];
            }
            if (savedStr == selectedStr) {
                cnt++;
            }
            else if (!flag) {
                newStr += cnt == 1 ? savedStr: to_string(cnt) + savedStr;
                savedStr = selectedStr;
                cnt = 1;
            }
        }

        newStr += cnt == 1 ? savedStr : to_string(cnt) + savedStr; // s.size()넘었을 경우 남은 str맨뒤에 추가 해줘야한다. 
        int sz = newStr.size();
        minSize = min(sz, minSize);

    }
    answer = minSize;
    return answer;
}
반응형