C,C++/코딩테스트
프로그래머스 2단계 - 문자열 압축
권멋져
2022. 6. 3. 17:36
https://programmers.co.kr/learn/courses/30/lessons/60057#
코딩테스트 연습 - 문자열 압축
데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문
programmers.co.kr
- 문제 파악
문자열을 m개로 묶을때 연속되는 같은 단어는 묶어서 표현할 수 있다. 이렇게 문자열을 압축할 때 가장 짧은 문자열의 길이를 출력하라.
- 정답
조금 더럽게 풀긴했는데 아예 압축된 문자열을 만들어서 그 길이를 계속 비교했다.
#include "bits/stdc++.h"
using namespace std;
int solution(string s) {
unsigned int answer = 0x7ffff;
if(s.size() == 1)
answer = 1;
int n = 1;
while(n < s.size())
{
string str_output;
string str = "";
int cnt = 0;
int i;
for(i = 0 ; i < s.size() - (n-1); i+= n)
{
string strtmp = s.substr(i,n);
if(str != strtmp)
{
str = strtmp;
str_output += str;
cnt = 1;
}
else
{
int pos = 0;
int tmp = cnt;
while(tmp != 0)
{
tmp = tmp/10;
++pos;
}
if(cnt > 1)
str_output.replace(str_output.size() - n - pos, n + pos,to_string(++cnt) + str);
else
str_output.replace(str_output.size() - n, n + 1, to_string(++cnt)+ str);
}
}
n++;
str_output += s.substr(i,s.size()- i);
if(answer >= str_output.size())
answer = str_output.size();
}
return answer;
}