지우너
[코드트리] 최단 Run Length 인코딩 C++ 본문
문제
계획 세우기
문자열을 오른쪽으로 한 칸 이동시키고, Run-Length Encoding을 적용
길이를 비교해서 작은 쪽으로 갱신하면 될 것 같다.
풀이
#include <iostream>
#include <climits>
using namespace std;
int RunLengthEncoding(string str){
string result;
char c= str[0];
int cnt=1, size = str.length();
for(int i=1; i<size; i++){
if(str[i]!=c){
result=result+c+to_string(cnt);
c=str[i];
cnt=1;
}
else cnt++;
}
if(cnt>1 || str[size-1]!=str[size-2]) result=result+c+to_string(cnt);
return result.length();
}
int ShiftStr(string str){
int answer=INT_MAX, size=str.length();
for(int i=0; i<size; i++){
//right shift
int lastElement = str[size-1];
for(int j=size; j>0; j--){
str[j]= str[j-1];
}
str[0]= lastElement;
//compare
answer = min(answer, RunLengthEncoding(str));
}
return answer;
}
int main() {
string inputStr;
cin >> inputStr;
cout << ShiftStr(inputStr);
return 0;
}
'Problem Solving' 카테고리의 다른 글
[코드트리] 십자 모양 폭발 C++ (0) | 2024.06.07 |
---|---|
[코드트리] 1차원 젠가 C++ (0) | 2024.06.06 |
[코드트리] 기울어진 직사각형의 회전 C++ (0) | 2024.06.05 |
[코드트리] 2차원 바람 C++ (0) | 2024.06.04 |
[코드트리] 1차원 바람 C++ (0) | 2024.06.03 |