알고리즘 풀이/프로그래머스
[프로그래머스][JAVA] 문자열 압축 (문자열)
배게
2022. 2. 23. 19:25
728x90
|
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
|
class Solution {
public int solution(String s) {
int answer = s.length();
// s.length()/2까지만 하면 됨
for(int i=1; i<=s.length()/2; i++){
String preUnit = "";
int accumNum = 1;
int compressedNum = s.length();
for(int j=0; j+i<=s.length(); j+=i){
// System.out.print(j+" ");
String currUnit = s.substring(j,j+i);
if(currUnit.equals(preUnit)){
accumNum++;
compressedNum-=i;
}
else{
if(accumNum>1)
compressedNum+=(Math.log10(accumNum)+1);
accumNum = 1;
preUnit = currUnit;
}
}
if(accumNum>1)
compressedNum+=(Math.log10(accumNum)+1);
// System.out.println(i+" "+compressedNum);
answer = Math.min(answer, compressedNum);
}
return answer;
}
}
|
cs |
|
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
|
import java.util.*;
class Solution {
public int solution(String s) {
int answer = s.length();
// ex) abc abc (idx1:0 idx2:3 idx3:3 idx4:6)
int startIdx = 0, unit = 1;
while(unit<=s.length()/2){
// int[] idx = makeIdxArr(startIdx, unit);
// for(int i : idx)
// System.out.println(i);
startIdx = 0;
int accumNum = 1;
String preStr = "";
int answerCandi = s.length();
// System.out.println((int)( Math.log10(10)+1 ));
while(true){
if(startIdx+unit>s.length()){
if(accumNum>1)
answerCandi+=(int)(Math.log10(accumNum)+1);
accumNum = 1;
answer = Math.min(answer, answerCandi);
break;
}
String currStr = s.substring(startIdx, startIdx+unit);
if(currStr.equals(preStr)){
accumNum++;
answerCandi -= currStr.length();
}
else{
/**
중복된 문자들 누적된 숫자 처리
**/
if(accumNum>1)
answerCandi+=(int)(Math.log10(accumNum)+1);
accumNum = 1;
}
preStr = currStr;
startIdx+=unit;
// break;
}
unit++;
}
return answer;
}
// public int[] makeIdxArr(int startIdx, int unit){
// int[] ret = new int[4];
// ret[0] = startIdx;
// ret[1] = startIdx+unit;
// ret[2] = ret[1];
// ret[3] = ret[2]+unit;
// return ret;
// }
}
|
cs |