[프로그래머스60057][C++] 문자열 압축

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

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

 

문제

주어진 문자열을 문자 1개 / 2개 / ... 단위로 나누어 압축하여 표현했을 때 가장 짧은 길이가 되는 경우를 구하는 문제이다.

ex) ababcdcdababcdcd의 경우

문자 1개를 단위로 하면 압축이 불가능하고,

2개로 하면 2ab2cd2ab2cd -> 12자리,

8개로 하면 2ababcdcd -> 9자리이므로

가장 짧은 경우는 8개를 기준으로 압축했을 때의 9자리이다.

 

해결

특별한 알고리즘 없이 조건에 맞게 구현하면 된다. 대신 모든 상황에 대입될 수 있게 꼼꼼히 따져가며 구현해야 한다. 대충 생각했다간 실패폭탄을 맞을 수 있다..

🧨초반에 삽질한 점 -> 문자열을 임의로 자를 수 없고 정해진 수만큼 앞부터 차례대로 무조건 잘라야 함 (주의)

 

1차시도 실패 - 테스트 코드 5개는 통과했는데 채점했더니 대참사..

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    answer = s.length();

    for (int n = 1; n <= s.length() / 2; n++) { // 단어 압축 단위(개수)
        int i = 0;  // 인덱스
        int cnt = 1;
        string result = "";
        string part1;
        string part2;
        while (i < s.length() && i + 2 * n <= s.length()) {	// 범위 예외처리
            part1 = s.substr(i, n); // i번째부터 길이 n만큼 추출	
            part2 = s.substr(i + n, n);
            if (part1 == part2) {
                cnt++;
            }
            else {
                if (cnt > 1) {
                    result += to_string(cnt);
                }
                result += part1;
                cnt = 1;
            }
            i += n;
        }

// 틀린 부분
        if (cnt > 1) {	// 반복된 수 남았을 때
            result += to_string(cnt);
            result += part1;
        }
        else {
            result += s.substr(i, s.length() - i);
        }
//
        if (result.length() < answer) answer = result.length();
    }

    return answer;
}

ㅠㅠ

🚨남은 문자 더하는 과정이 문제였음.

반복된 수가 남아있는 경우에서 그 이후에 나오는 반복되지 않는 수(범위 예외처리에서 걸려 스캔되지 못하고 남은 수)가 더해지지 않아 발생한 문제였다.

그래서 else문에 있는 문장을 밖으로 빼고 else문을 없애서 항상 남은 수가 모두 더해지도록 했더니, 또 실패했다. vs로 코드를 옮겨 테스트 결과를 찍어봤더니, 반복된 수가 part1에 남고(인덱스 i가 이 수 이전에 멈춰있는 상황임) if문에서 part1을 더해줬는데 i 이후로 남은 수를 모두 더할 때 이부분이 중복으로 더해졌던 것이다. (말 표현이 이상한데 암튼 그런..)

=> 반복된 수가 남은 경우에는 반복횟수만 따로 더해주고, 마지막에는 항상 남은 문자를 모두 더해주면 된다!

 

2차 시도 성공!

예시와 함께 코드를 간단히 설명해보자면,

주어진 문자열 = "ababcd" 라고 하자.

 

1) n = 1

i = 0에서 시작

part1 = a, part2 = b

=> part1 != part2

result = "a"

-> i = 0 + 1 = 1

... (반복되는 한자리 문자가 없으므로 answer값 변화 x)

 

2) n = 2

i = 0

part1 = ab, part2 = ab

=> part1 == part2

-> cnt = 2, i = 0 + 2 = 2

 

part1 = ab, part2 = cd

=> part1 != part2

part1과 part2가 같지 않은 상황에서, 이전에 반복된 문자의 카운트 값이 저장되어 있으므로(이 카운트 값은 지금 단계에서의 part1의 문자가 반복된 횟수이다) 카운트 값을 문자열에 더해주고, part1 문자를 더해준다.

result = "2", result = "2ab"

-> i = 2 + 2 = 4

 

범위 예외처리에 의해 while문을 빠져나오게 된다.

반복되는 문자열이 남아있지 않으므로(현재는 "cd"만 남은 상태) 남은 문자열을 최종 문자열에 모두 더해준다

=> result = "2abcd"

 

밑에 if문으로 반복된 문자가 남았을 때 반복횟수 더해주는 코드가 처리해주는 경우는 주어진 문자열이 "abababcd"일 때를 생각해보면 된다. 마찬가지로 n = 2 일 때, 범위 예외처리로 인해 while문이 끝났을 때 i는 4이고 남은 문자열은 "abcd"이다. 반복된 ab의 누적값 3을 최종 문자열에 더해주고, 남은 문자열을 그대로 더하면 정답인 "3abcd"를 얻을 수 있다.

 

** 정답은 최종 문자열이 아닌 문자열 길이를 출력해야 함! **

[전체 코드]

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    answer = s.length();

    for (int n = 1; n <= s.length() / 2; n++) { // 단어 압축 단위(개수)
        int i = 0;  // 인덱스
        int cnt = 1;
        string result = "";
        string part1;
        string part2;
        while (i < s.length() && i + 2 * n <= s.length()) {	// 범위 예외처리
            part1 = s.substr(i, n); // i번째부터 길이 n만큼 추출
            part2 = s.substr(i + n, n);
            if (part1 == part2) {
                cnt++;
            }
            else {
                if (cnt > 1) {
                	result += to_string(cnt);
                }
                result += part1;
                cnt = 1;
            }
            i += n;
        }

        if (cnt > 1) {
            result += to_string(cnt);	// 반복된 문자 남았으면 반복횟수 더해주기
        }
        result += s.substr(i, s.length() - i);	// 남은 문자 다 더하기
      
        if (result.length() < answer) answer = result.length();
    }

    return answer;
}