문제
- 문자열에서 같은 값이 "연속"해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있다.
- 그 문자의 개수와 반복되는 값으로 표현 —> "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)
- 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점—→ 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않음.
- 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다. —> "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법
- "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법 . (abc abc dede . 즉 dede 처럼, 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 된다)
- 문제에서 구하라고 하는 것 : 압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성
문제 이해가 잘 안된 것 같으니 예시를 보자.
-
abcabcdede 는 길이가 10이다.
< 이해 해보자 >
- n을 3이라고 한다면 0 , 3, 6, 9에서 확인한다.
- i+n > s.length 이면 Stop 하고 s.length-i 을 하면 단위로 잘리지 않고 [ 남은 문자열 ]의 길이를 의미한다.
-
"aabbaccc" —> 2a2ba3c
-
"ababcdcdababcdcd" —>
- 만약 2개 단위로 잘라 압축 시, 오히려 숫자로 인해 길이가 더 길어진다. 2ab2cd2ab2cd —> 12
- 반면 8개 단위로 잘라 압축 시, 2ababcdcd 로 —>9
-
"xababcdcdababcdcd" —> 이 예제를 통해 헷갈리던 부분을 해결함
- 헷갈리던 것 : n개 단위인 경우, x에서 n개인 문자열이 연속하여 반복되는 게 없으면, 여기서 index를 1 증가시켜, a부터 n개를 보는 식인가 ? —> NO
- 항상 n개 단위로만 성공하고 실패한다. 즉, 맨 처음부터 n개를 보고, 반복이 아니라면, i+n 위치의 것을 확인한다. i+1위치의 것을 확인하는게 아니다.
-
n 개 단위로 자른다고 한다면 idx?
- i에서 반복이 일어나는지 확인한다.
- HOW????
- 예를들어 abab인 경우, 2개단위라하면 n=2이고, i=0일 때는, i+n 에서 ab가 있어야 —> 연속하여 반복이라 할 수가 있다.
- n 개 단위로 매 번 앞의 것과 반복인지를 확인한다. 반복이 아니면, 앞의 문자열을 그대로 두고(결과 문자열의 길이에, n을 더한다. ),
- 언제까지 ? i + n 이 s.length보다 작을 때 까지.
- i에서 반복이 일어나는지 확인한다.
문제 해결
-
걍 단순하게 생각나는 것
- 길이가 1000이하이기 때문에, 완전탐색을 하더라도 괜찮을 것 같다.
- 단위 n 을 1부터 n까지 전체 탐색
그리디하게 풀어야 할까 ????
-
반복되는 문자열 중 " 가장 길이가 긴 것" -
문자열의 "반복되는 수가 가장 많은 것 "아 이 방식은 아니다.그저 완전탐색을 해야 할 것 같다.
- 문제에서 오해하지 말아야 할 것. "n개"단위로 문자열을 자른다고 하면, n개 이외의 단위로는 자를 수 없다. 예를들어 위에서 예시를 든 것도, 3개 단위로 문자열 자르는 경우 2개로도 자를 수 있음에도 2개로 자를 수 있는 것은 배제 시켰다.
- 길이가 1000이하이기 때문에, 완전탐색을 하더라도 괜찮을 것 같다.
-
사용할 String class의 메소드 에 대한 고민
- substirng?
- 일단 아주 단순하게(그리고 효율이 안나게) 매번 String생성하기.
- substirng?
-
먼저 특정 문자열이 "연속해서 반복되는 횟수" 를 구하는 메소드 작성
- 특정 문자열이 "연속해서 반복하는가"를 찾기
- 몇 번 반복하는지 찾기
-
str.substr(i,i+n)
-
update i= i +n
-
str.substr(i,i+n) 과 같은지를 확인.
public int checkRepeat(String s, int idx,int n){ // 기준은 String target = s.substr(idx,idx+n); int cnt =0; // 반복한다. int i = idx+n; while(i+n<=s.length){ String cur = s.substr(i,i+n); if(cur.eqauls(target)) cnt++; else break; } return cnt; }
- 여기서 return 한 값 x n 만큼 한 곳부터 다음 idx가 되는 것.
class Solution {
public int min = Integer.MAX_VALUE;
public int solution(String s) {
int answer = 0;
int len = s.length();
int totCnt =0; // 전체 문자열의 길이를 기록한다.
int curCnt =0; // 현재 문자열의 반복횟수를 기록한다.
// 모든 경우에 대한 탐색을 시행한다.
for(int n =1; n<=len;n++){
totCnt =0;
int startIdx=0;
while(startIdx+n<=s.length()){
curCnt = checkRepeat(s, startIdx, n);
startIdx+=n*curCnt;
totCnt+=n;
// 반복 된 경우, 반복 횟수도 길이에 더해줘야한다. 1이면 1, 11이면 2, 111이면 3을 더해줘야 한다.
if(curCnt>1) totCnt+=String.valueOf(curCnt).length();
}
// 남은 길이를 더해줘야 한다. 예를들어 예제 3번 처럼."abcabcdede"의 경우, idx 9의 경우 9 + 3 >10 이기 때문에, while문을 벗어난다.
// "e" 에 해당하는 길이를 더해줘야한다.
totCnt += (s.length()-startIdx);
if(totCnt<min) {
min = totCnt;
}
}
answer = min;
return answer;
}
// idx부터 idx+n 까지의 문자열이 반복되는지 구한다.
// 리턴 값이 1인 경우 --> 반복이 없다 .
// 리턴 값이 1보다 큰 경우 --> 반복하는 횟수가 리턴된다.
public int checkRepeat(String s, int idx, int n){
if(idx+n>s.length()) return 1;
String target = s.substring(idx,idx+n);
int cnt = 1;
int i = idx+n;
while(i+n<=s.length()){
String next = s.substring(i,i+n);
if(next.equals(target)) {
i+=n;
cnt++;
}
else break;
}
return cnt;
}
}자리수 구하기 다른 방법
- 다른 분의 풀이를 보니 Math.log10(..)을 사용하셨다.
- 이 문제에서는 abcabc의 경우 --> 2abc가 된다. 여기서 "2"도 압축결과문자열의 길이에 포함되기에 이를 구하기 위해 나는
int len = String.valueOf(length);를 하였는데 생각해보면
log10(111) 의 경우 2 가 나온다. 그러니 여기다 1만 더해주면 됨
log10(9) + 1 은 1이니 한 자리 수 라는게 맞다.
int len = Math.log10(length)+1;