![[프로그래머스,Level 2] 문자열 압축(JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FtHo2Y%2FbtqTvQYxVcg%2FwNdiNhwBeoUVDn1wWTspXk%2Fimg.png)
- 첫 풀이
문자열 관련 문제에 약해서 이리저리 만져보려고 했지만, 잘 풀릴 기미가 보이지 않아 다른 분들의 풀이에서 힌트를 좀 얻고자 했다. 대부분의 분들이 substring() 메서드를 이용해 풀이를 하고 있었고, 풀이 방법이 다양해 필자는 substring()을 나만의 방식으로 이용해 보고자 했다. 문제에 조건대로 이리저리 건드려 보았더니 다른 분들의 풀이에서 본 수식과 동일한 형태가 나오기 시작하였고, 해결할 수 있었다.
- 정답풀이
우선 이 문제의 핵심은 substring(begin, end) 메서드라고 생각된다. substring() 메서드는 begin에 시작 인덱스, end에 끝 인덱스를 입력하면 begin 인덱스 ~ (end 인덱스-1)까지의 문자열을 반환한다. 그리고 든 처음 생각은 substring() 메서드에 사용할 인덱스를 건드려보기로 했다.
또한, 이 문제에서 문자열을 나눌 수 있는 범위는 1~s.length()/2까지가 될 수 있다. 예제 입력 1의 경우 길이 4까지 문자열을 압축할 수 있는데, 5 이상이 안 되는 이유는 문제에서 제시하듯 앞에서부터 5를 나누어보면 5/3으로 나누어지기 때문에 압축이 불가능해지게 된다.
1번 입력 예제를 문자열을 1 크기로 압축한 결과를 인덱스 별 표로 표시하면 아래와 같다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| a | a | b | b | a | c | c | c |
이는 substring을 사용할 때, 아래와 같이 표현할 수 있다.
| substring(0,1) | substring(1,2) | substring(2,3) | substring(3,4) | substring(4,5) | substring(5,6) | substring(6,7) | substring(7,8) |
| a | a | b | b | a | c | c | c |
위와 같은 방식으로 2, 3, 4크기로 압축하는 경우 substring() 메서드의 인자로 들어가는 순서는 2일 때 (0,2) (2,4)... 3일 때 (0,3) (3,6)... 4일 때 (0,4) (4,8)....로 인덱스가 사용되어진다. 이러한 규칙을 바탕으로 반복문을 세우면, 아래와 같다.
// 문자열 압축 범위 1~s.length()/2
for(int i =1;i<=s.length()/2;i++){
// 가장 마지막 압축의 begin 인덱스 범위까지
// ex. 길이 3으로 압축 시 substring(0,3), substring(3,6)으로 압축 가능.
// j는 8/3 = 2로, 0~1까지 반복. 여기에 길이를 곱하면 0, 3이나온다.
// 이를 이용해 substring에 표현, 나머지 길이 압축 과정에서 규칙성을 찾을 수 있다.
for(int j =0;j<s.length()/i;j++){
s.substring(j*i,(j*i)+i)
}
}이렇게 substring()으로 자른 문자열들을 비교해 같은 개수만큼 카운팅하여 개수+자른 문자열로 압축하는 과정을 거친다. 이때 카운팅이 1개인 즉, 압축이 안 되는 경우는 예외처리로 자른 문자열만 붙여줘야 한다.
for(int i =1;i<=s.length()/2;i++){
// 길이 별 압축된 문자열이 저장 될 변수.
String str = "";
// 길이 별로 자른 문자열을 비교하기 위한 변수.
String temp="";
// 자른 문자열 중 같은 문자열을 카운팅.
int count = 1;
for(int j =0;j<s.length()/i;j++){
// 이전에 자른 문자열과 이제 자른 문자열이 같으면 카운팅.
if(temp.equals(s.substring(j*i,(j*i)+i))){
count++;
continue;
}
// 카운팅이 1이상인 경우, 숫자 + 자른 문자열.
if(count >1){
str+=count+temp;
count = 1;
// 카운팅이 1인 경우, +자른 문자열.
}else{
str+=temp;
}
// 비교대상 변경.
temp=s.substring(j*i,(j*i)+i);
}
}
마지막으로, 예제 1번과 같이 마지막에 압축되는 경우는 continue; 처리로 인해 다 빠져 나오므로 남아있는 압축 문자열을 붙여준 뒤, 길이 3과 같이 s.length() % 3!= 0 인 경우는 마지막 부분에 남는 문자열을 최종 문자열에 붙여주어야 한다.
class Solution {
public int solution(String s) {
// 1. 최소 문자열을 찾기 위한 비교 변수.
int answer =Integer.MAX_VALUE;
// 2. 문자열 길이가 1인 경우는 압축 불가로 1 반환. 안하면 테스트 케이스 1개에 걸린다.
if(s.length() == 1) return 1;
// 3. 1~s.length()/2 만큼 압축가능.
for(int i =1;i<=s.length()/2;i++){
// 압축 길이 별 문자열 변수.
String str = "";
// 자른 문자열을 비교 할 변수.
String temp="";
// 자른 문자열의 개수를 카운팅 할 변수.
int count = 1;
// substring()의 범위만큼 반복.
for(int j =0;j<s.length()/i;j++){
// 4. 이전에 자른 문자열과 현재 자른 문자열이 같다면 카운팅.
if(temp.equals(s.substring(j*i,(j*i)+i))){
count++;
continue;
}
// 5. 카운팅 > 1인 경우는 count+temp 후 count 초기화.
if(count >1){
str+=count+temp;
count = 1;
// 6. 나머지의 경우는 자른 문자열인 temp만 붙여준다.
}else{
str+=temp;
}
// 7. 현재 자른 문자열로 비교대상 변경.
temp=s.substring(j*i,(j*i)+i);
}
// 8. 마지막에 붙이지 못한 문자열을 붙인다.
if(count >1){
str+=count+temp;
count = 1;
}else{
str+=temp;
}
// 9. s의 길이가 압축하는 길이로 나누어 떨어지지 않는 경우, 나머지 부분부터 마지막까지 substring을 이용해 붙인다.
if(s.length()%i !=0){
str+=s.substring(s.length()-s.length()%i,s.length());
}
// 10. 가장 짧은 길이를 찾음.
answer = answer > str.length() ? str.length() : answer;
}
return answer;
}
}