X - [ 구현 ] 문자열 압축 - R - r

난이도 : 중하  풀이시간 : 30/54  시간제한 : 1초  기출 : 2020 카카오 신입 공채

 

문제 링크 : 코딩테스트 연습 - 문자열 압축 | 프로그래머스 (programmers.co.kr)

 

---

  아이디어  

어제 답안을 보고

오늘 아무것도 안 보고 혼자 다시 짜봄 !

여러번 고치긴 했지만 맞음 >< 

 

잘 몰랐던 부분

1. 마지막으로 자른 문자열을 처리하는 법

2. 자르는 문자열의 단위는 1~문자열의 절반 인데 2~라고 생각했음

3. string 함수들 => to_string, substr 등의 정확한 사용법

 

아이디어 ! 

1. 처음 문자열의 길이를 min 변수에 저장

2. 한자리부터 문자열길이/2까지 반복문 

  i ) 문장 처음부터 해당하는 길이만큼 문장을 잘라서 before에 저장

 ii ) 그 다음으로 자른 게 before와 같으면 cnt++;

     다르면 cnt 를 확인하고 cnt가 1보다 큰 경우 숫자랑 before 문자열이랑 같이 붙여서 압축문자열에 더해줌

                                    cnt가 1인 경우 1은 생략하고 before 문자열만 압축문자열에 더해줌

      그 후에 before에 자른 문자열을 넣고 cnt 를 1로 초기화 해줌

3. 해당 단위 반복문이 끝나면 cnt를 체크해서 위의 과정을 한번 더 해줌

4. 그러고 min의 값과 완성된 압축문자열의 길이를 비교해서 더 작은 수치를 min에 기록

5. 모든 반복문이 끝나면 min 값 리턴

 

  내   코드  

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string s) {
    
    int min = s.size();
    
    string sub;
    string before;
    int cnt;

    for (int i = 1; i <= s.size()/2; i++) {
        string comp = "";
        before = s.substr(0, i);
        sub = "";
        cnt = 1;
        for (int j = i; j < s.size(); j += i) {
            sub = s.substr(j, i);
            if (sub == before) { cnt++; }
            else { 
                if (cnt > 1)
                    comp += to_string(cnt) + before;
                else comp += before;
                before = sub;
                cnt = 1;
            }
        }
      
        if (cnt > 1) {
            comp += to_string(cnt) + before;
        }
        else comp += before;

        if (min > comp.size()) {
            min = comp.size();
        }
    }

    return min;
}

 

  정답  코드  

#include <bits/stdc++.h>

using namespace std;

int solution(string s) {
    int answer = s.size();
    // 1개 단위(step)부터 압축 단위를 늘려가며 확인
    for (int step = 1; step < s.size() / 2 + 1; step++) {
        string compressed = "";
        string prev = s.substr(0, step); // 앞에서부터 step만큼의 문자열 추출
        int cnt = 1;
        // 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
        for (int j = step; j < s.size(); j += step) {
            // 이전 상태와 동일하다면 압축 횟수(count) 증가
            if (prev == s.substr(j, step)) cnt += 1;
            // 다른 문자열이 나왔다면(더 이상 압축하지 못하는 경우라면)
            else {
                compressed += (cnt >= 2)? to_string(cnt) + prev : prev;
                prev = s.substr(j, step); // 다시 상태 초기화
                cnt = 1;
            }
        }
        // 남아있는 문자열에 대해서 처리
        compressed += (cnt >= 2)? to_string(cnt) + prev : prev;
        // 만들어지는 압축 문자열이 가장 짧은 것이 정답
        answer = min(answer, (int)compressed.size());
    }
    return answer;
}

 

  리뷰  

저번 풀이시도 때도 문제를 잘못 이해해서 못 풀었는데

이번에도 문제를 잘못 이해함

문제에서는 aabbaabb의 경우 

2a2b2a2b 혹은 2aabb 로

연속된 문자열을 압축하는 것을 말하는데

나는 문자열이 연속되어 있지 않아도 압축에 포함시켜

4a4b 이런 식으로 압축하는거라고 생각해서 코드가 복잡해진데다 결과값도 틀리게 나왔음

 

다시 풀어봐야함

 

-----------------------------------------------------------------------------------------------------------------------------------

 

다시 풀었당 !!!!

근데 확실히 string 함수들을 잘 모르는 듯 전에 공부도 한번 했었는데 

이번 기회에 완전히 외우고 넘어가는 게 좋을 듯 함