https://programmers.co.kr/learn/courses/30/lessons/60057#
접근
solution 함수에서 다중 for문으로 처리 가능하나 가독성 및 디버깅을 위해 compress 함수를 만들어서 풀이 진행. compress는 길이와 문자열을 매개변수로 받고 길이만큼 문자열을 잘라서 크기를 리턴해줌.
compress에서 먼저 비교할 단어를 substr 이용해 bigo문자열에 넣어주고 비교할 문자열을 jstring에 넣어서 2중 for문으로 진행한다.
주의할점 - k는 문자열 시작위치를 나타내는데, 압축단어를 찾고나면 그길이만큼 건너뛰게해야한다. 하지만 for문에서 k길이는 cnt만큼 (압축할길이) 증가하므로 wordcnt * cnt - cnt를 이용해 한번의 cnt길이만큼을 빼줘야 위의 첫 for문으로 올라가면서 cnt가 다시 더해져서 원래 의도만큼 압축된 길이를 건너뛰고 시작할 수 있다.
*테스트케이스 - 10개이상 압축되는 경우가 있으므로 to_string을 이용해 압축 숫자표현해야함. + '0' 방식으로 숫자 문자열 추가시 0~9까지만 추가가됨.
#include <bits/stdc++.h>
using namespace std;
int compress(string a,int cnt){
string ans="";
for(int k=0;k<a.size();k+=cnt){
string bigo = a.substr(k,cnt);
int wordcnt = 0;
for(int j=k;j<a.size();j+=cnt){
string jstring = a.substr(j,cnt);
// cout<<"jstring"<<jstring<<endl;
if(bigo == jstring)wordcnt++;
else break;
}
k+= wordcnt*cnt-cnt; // 위에 for문 올라가면서 k+=cnt 연산자때매 원래 위치보다 한번 더 이동
if(wordcnt > 1)ans+= to_string(wordcnt);
ans+=bigo;
}
cout<<ans<<endl;
return ans.size();
}
int solution(string s) {
int leng = s.size();
int answer = s.size();
for(int i=1;i<s.size();i++){ // 문자열 자를 단위 2부터 , 안자르면 기본 길이 이므로
answer= min(compress(s,i),answer);
}
return answer;
}
'알고리즘 풀이' 카테고리의 다른 글
[Phthon] 백준 1158 요세푸스 문제 (0) | 2021.09.02 |
---|---|
[백준] 1051번 숫자 정사각형 (C++) (0) | 2021.05.31 |
[백준] 10819번 차이를 최대로 , 순열문제 (0) | 2021.05.26 |
[백준] 16945 매직스퀘어로 변경하기 (순열을 이용한 풀이) (0) | 2021.05.24 |
[백준] 1120 문자열 - 완전탐색 (0) | 2021.05.12 |