C++ 학습/C++ 코딩인터뷰[6장]
[6. 문자열] 6.11 반복 길이 부호화로 문자열을 압축/해제하기
msugi
2025. 2. 13. 10:37
[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include "Q6.h"
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
os << "[";
for (size_t i = 0; i < vec.size(); i++)
{
os << vec[i];
if (i != vec.size() - 1)
{
os << ", ";
}
}
os << "]";
return os;
}
|
cs |
|
|
// main에서 vector 형태로 출력하기위한 기본 셋팅
|
Q 6.11 반복 길이 부호화로 문자열을 압축/해제하기
반복 길이 부호화(RLE) 는 압축 및 해제를 실시간으로 수행할 수 있는 효과적인 압축 방법이다.
해당방법은 다음과 같다.
실제 문자열 대신 문자와 해당 문자의 연속 등장 횟수를 함께 써 주면 된다.
예를 들어 "aaaabcccaa"를 RLE로 압축하면 "4a1b3c2a" 가 되며,
"3e4f2e"를 압축 해제하면 "eeeffffee" 가 된다.
해당 문제의 소스코드와 결과는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
// 6.11 반복 길이 부호화로 문자열을 압축/해제하기
#include <string> std::string Decoding(const std::string& s)
{
int count = 0;
std::string result;
for (const char& c : s)
{
if (isdigit(c))
{
count = count * 10 + c - '0';
}
else
{
result.append(count, c);
count = 0;
}
}
return result;
}
std::string Encoding(const std::string &s)
{
std::string result;
for (int i = 1, count = 1; i < size(s); i++)
{
if (i == size(s) || s[i] != s[i - 1])
{
result += std::to_string(count) + s[i - 1];
count = 1;
}
else
{
count++;
}
}
return result;
}
|
cs |
문자열의 길이를 n이라고 했을 때 전체 시간 복잡도는 O(n)이다.
|
1
2
|
// main
std::cout << "6-11 " << Encoding("aaaabccaa") << std::endl; //6-11 std::cout << "6-11 " << Decoding("4a1b2c2a") << std::endl; //6-11
|
cs |
