-
Notifications
You must be signed in to change notification settings - Fork 1
/
문자열 압축.cpp
94 lines (76 loc) · 2.18 KB
/
문자열 압축.cpp
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 문자열 압축
// https://programmers.co.kr/learn/courses/30/lessons/60057
// 시행착오
// 1. 문자열을 무조건 제일 앞부터 잘라야 한다는 조건을 제대로 읽지 않았음.
// 2. 한번 자른 문자열이 계속 나타나는지 확인하는것이 아니라,
// 고정된 크기로 자른 문자열이 연속적으로 같은지 판단해야하는데 이 부분을 잘못 이해함
// 3. 탐색 범위 (i < s.size() / 2) -> (i <= s.size() / 2)
// 4. 아무런 답도 얻지 못하는 경우 input의 길이를 반환해야함 (한 글자 예외처리 중 발견)
#include <iostream>
#include <string>
#include <vector>
//#include "Print.h"
using namespace std;
int Compress(const string& target, int size)
{
int start = 0;
int cnt = 0;
vector<int> counts;
string substr = target.substr(start, size);
string prev = substr;
while (true)
{
size_t i = target.find(substr, start);
if (i == string::npos)
break;
if (prev == substr)
{
cnt++;
}
else
{
if (cnt > 1)
counts.push_back(cnt);
cnt = 1;
}
start = i + size;
if (start >= target.size())
break;
prev = substr;
substr = target.substr(start, size);
}
if (cnt > 1)
counts.push_back(cnt);
int sum = 0;
for (auto c : counts)
{
int discount = (c - 1) * size - to_string(c).size();
sum += discount;
}
int ret = target.size() - sum;
//Print::Container(counts);
return ret;
}
int solution(string s)
{
int answer = s.size();
for (int i = 1; i <= s.size() / 2; ++i)
{
int cnt = Compress(s, i);
answer = min(answer, cnt);
}
return answer;
}
int main()
{
//string input = "a";
//string input = "aabbaccc";
//string input = "ababcdcdababcdcd";
//string input = "abcabcdede";
//string input = "aaaaaaaaaaaaaaaaaaaaaaa";
//string input = "abcabcabcabcdededededede";
string input = "xababcdcdababcdcd";
int answer = solution(input);
cout << "answer : "<< answer;
return 0;
}