[프로그래머스] 2020 KAKAO BLIND RECRUITMENT Lv2.문자열압축

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

스케치

처음으로 프로그래머스 Lv2에 도전해봤다!
문제를 읽다보니 헤매면 정말 오래 헤맬 거 같아서 정신을 똑바로 차려야겠다고 생각했다..ㅋㅋ

문제 해결 과정

그래서 이번에는 스케치할 때 1개~3개 단위 압축 단계를 손으로 시뮬레이션 해보면서
변수나 예외처리 등등을 더 여러 번 고민해보았다

문자열을 계속 여러번 순회해야 한다는 점이 시간초과에 걸리지 않을까 불안했고
최대한 반복 횟수를 줄여야겠다고 생각했다

그래서 가장 먼저 간단하게 몇 개 단위까지 검사해봐야하는가?를 고민했다
단위가 문자열 길이의 절반+1 이상이 되는 경우, 1개 이상의 반복이 나오지 않기 때문에 무의미했다
ex) length가 8인 경우 단위 5부터는 의미가 없음
그래서 딱 문자열 길이의 절반까지만 단위를 검사하도록 했다

그 다음으로는 단위별로 문자를 가져오는 것인데
처음에는 문자열에서 캐릭터 한 개씩 뽑아서 단위 길이에 맞는 문자열을 만들도록 하는 방법을 구상했었다
근데 이럴 경우 단위가 1이든, 2이든, 10이든, 문자열 길이만큼 반복을 해야해서 효율적이지 않아 보였다!

그래서 substr을 이용해 단위길이만큼 문자열을 가져오도록 했고,
반복문에서도 unit만큼 건너뛰어서 반복 횟수를 줄였다

이 문제를 풀 때,
먼저 압축부분을 구현하고 나서 압축 문자열의 가장 짧은 길이의 구하는 부분을 구현했다
이렇게 나름의 모듈단위로 나눠서 구현해보니,
먼저 구현된 압축부분의 테스트가 완료되어서 가장 짧은 길이를 구할 때
원하는 기대결과가 나오지 않는 경우 짧은 길이를 구하는 부분의 코드만 신경쓰면 된다는 점이 편했던 것 같다!

다 하고나서 정답은 맞긴 했는데
다시 보니까 불필요하게 코드가 반복되는 부분이 보여서 수정했다!
한 10줄 정도 줄일 수 있었다

한 가지 스케치랑 달라진 점은
현재 문자열을 저장해놓는 t말고도 다음 문자열을 저장하는 변수가 필요했다
매 반복마다 curT와 nextT를 비교해서 그에 따른 처리를 해야했기 때문이다

배운 점

1. string의 substr(pos, count)

string s = "abcabcdede"
cout<<s.substr(0, 3)<<endl // abc

- 문자열의 pos 번째 문자부터 count 길이만큼 문자열의 일부를 가져온다

2. string의 compare

• 부끄럽지만 쓸 때마다 헷갈리는데 string이 일치하는 경우 0을 반환한다
• 반복문에서 if(curT.compare(nextT)) 이런식으로 하면 두 문자열이 다른 경우를 조건으로 하는 것이다

수정된 코드

#include <iostream>
#include <string>
using namespace std;

int solution(string s) {
    string curT, nextT, result;
    
    int count = 1;
    int len = s.length();
    int answer = len;
    
    for(int unit=1; unit<=(len/2); unit++)
    {
        curT = s.substr(0, unit);

        int i = unit;
        while (true)
        {
            /* 예외: 남은 글자 수가 단위보다 적은 경우 */
            if(i+unit > s.length())
            {
                if (count > 1)
                    result.append(to_string(count));
                result.append(curT);

                for (int j = i; j < s.length(); j++)
                    result.push_back(s[j]);
                break;
            }

            nextT = s.substr(i, unit);

            if (!curT.compare(nextT))
            {
                count++;
            }
            else
            {
                if (count > 1)
                {
                    result.append(to_string(count));
                    count = 1;
                }
                
                result.append(curT);
                curT = nextT;
            }
            i += unit;
        }

        if(answer > result.length())
            answer = result.length();   

        result.clear();
        count = 1;
    }
    
    return answer;
}

수정 전 코드

#include <iostream>
#include <string>
using namespace std;

int solution(string s) {

    string curT;
    string nextT;
    string result;
    
    int count = 1;

    int len = s.length();
    int answer = len;
    for(int unit=1; unit<=(len/2); unit++)
    {
        curT = s.substr(0, unit);

        int i = unit;
        while (true)
        {
            if (i + unit <= s.length())
            {
                nextT = s.substr(i, unit);
            }
            else
            {
                if (count > 1)
                {
                    result.append(to_string(count));
                }
                result.append(curT);

                for (int j = i; j < s.length(); j++)
                {
                    result.push_back(s[j]);
                }
                break;
            }


            if (!curT.compare(nextT))
            {
                count++;
            }
            else
            {
                if (count > 1)
                {
                    result.append(to_string(count));
                    result.append(curT);
                    count = 1;
                }
                else
                {
                    result.append(curT);
                }
                curT = nextT;
            }
            i += unit;
        }
        
        if(answer > result.length()) 
            answer = result.length();
    
        result.clear();
        count = 1;
    }
    return answer;
}