2020 카카오 신입사원 코딩테스트 - 문자열 압축

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

코딩테스트 연습 - 문자열 압축 | 프로그래머스

 

 

 

카카오 코딩테스트는 어렵기로 유명합니다.

당분간 카카오 코딩테스트 풀이를 올릴 예정입니다.

 

이번 문자열 압축 문제는 단순 for문을 이용한 완전탐색 문제입니다.

 

이러한 문제에서 알아두면 좋은 팁이 몇 개 있습니다.

 

1. str.substr(시작위치, 문자열 길이);    원하는 위치에서부터 원하는 길이만큼 문자열을 자르는 아주 유용한 함수!

2. stack을 사용하거나 string을 자르는 문제의 경우 항상 for문이 끝나고 처리되지 않는 것들이 남아있는지 반드시 확인한다!!(매우 중요)

 

이 알고리즘 시간복잡도는 O(N^2)가 되겠습니다.

 

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(string s) {
    int ans = s.size();
    string pattern = "";
    int l = s.size();
    
    
    // 이것을 처리하는 방법에는 여러가지가 있다
    // 여기에서는 이렇게 처리한다
    // 1. 현재 위치에서 i 길이만큼 잘라 pattern을 만든다
    // 2. 다음 위치에서 i 길이만큼 자른 문자열과 pattern이 일치하는지 확인한다
    // 3-a. 일치한다면, cnt += 1을 하고 다음 위치로 넘어간다
    // 3-b. 일치하지 않는다면, tmp_ans += i + (cnt 길이)를 해주고, cnt = 1, pattern = (현재 위치에서 길이 i 만큼 자른 문자열) 로 초기화해준다.
    
    for(int i = 1; i <= l / 2; ++i){
        int cnt = 1;                        // 패턴과 같은 문자열이 몇 개 있는지 기록하기 위한 변수
        int tmp_ans = 0;
        pattern = s.substr(0, i);
        
        int limit = l / i;
        for(int j = 1; j < limit; j++){     // 한 번에 길이 i 만큼씩 볼 것이다.
            string sub = s.substr(j*i, i);  // j*i는 현재 위치이고, 여기서부터 길이 i만큼 문자열을 자른다
            if(sub == pattern){
                cnt += 1;
            }
            else {
                tmp_ans += i;
                if(cnt > 1) {
                    int tmp_cnt = cnt;
                    while(tmp_cnt) tmp_ans += 1, tmp_cnt /= 10;
                }
                pattern = sub;
                cnt = 1;
            }
        }
            
        // 어떤 경우에서든 위 for문의 else 블럭에서
        // tmp_ans += i 등의 구문이 실행되지 않고 끝나게 된다
        // 짧은 예제를 통해 직접 손으로 써가며 시뮬레이션을
        // 하게 된다면 무슨 뜻인지 바로 알 수 있을 것이다!
        
        
        // 이러한 것은 보통 stack, string 관련 문제를 풀 때
        // 가장 많이 실수 하는 부분 중에 하나이다!! (중요)
        tmp_ans += i;
        if(cnt > 1) {
            int tmp_cnt = cnt;
            while(tmp_cnt) tmp_ans += 1, tmp_cnt /= 10;
        }
        
        
        // 이 코드 또한 실수할 여지를 주는 부분이다
        // 만약 s의 길이가 5이고 패턴의 길이를 2로 자르게 되면
        // 맨 뒤에 1개의 문자가 처리되지 않고 남아있게 된다!
        // 이것을 더해주어야 한다
        tmp_ans += l % i;
        
        ans = min(ans, tmp_ans);
    }
    
    return ans;
}