[프로그래머스] 문자열 압축
두 번째로 풀 때
문자열의 길이를 이용하는 식으로 풀이하였다.
- 문자열을 직접 생성하는 것은 아닌 것 같아서, 오로지 index를 사용하여 풀이했다.
- 따라서, 자르는 단위를 u로 하여, 압축된 문자열의 길이를 구하기 위해 u씩 더해가는 방식을 취했다.
- 남는 문자열은 따로 더해준다.
문자열 s에서
[ i ... i + u -1 ] 과 [ i+u ... i +u+u-1 ] 이 동일한지 확인해야한다.
i를 pre로 , i+u를 cur 로 한다.
- 이 때 주의할 것들이 여러개 생긴다.
- cur + u > len 이라면 , [ cur + u ... ] 은 단위 u에 못미치는 접미사 임을 듯한다. 따라서 이는 나머지 부분으로 계산해야한다.
- cur문자열과 pre문자열을 비교한다. 어차피 둘다 길이 u의 것이다.
- 둘이 같은 경우, pre문자열의 개수를 +1
- 둘이 다른 경우, pre 문자열의 개수를 확인한다.
- 1개라면 → 문제에서는 1개의 경우는 “1”을 표시하지 않는다고 했기 때문에 넘어간다.
- 1개보다 크다면 → 해당 정수를 문자열으로 변환시, 길이가 몇인지를 계산하여 total length에 더해준다.
- 주의할 상황
- 나는 while문 내부에서, cur문자열과 pre문자열의 비교를 진행했다. 그러다보니, 계속해서 pre,cur이 동등하다가 while문이 종료된 경우 → total length에 update를 진행하지 못한 경우가 생겼다.
- 따라서 while문이 종료된 이후에도, ucnt가 1보다 큰지 확인하여 → 해당 ucnt 를 문자열로 변환하였을 때 길이를 더해주는 과정을 빼먹어선 안됐다.
어차피 “abcabc”에서 u가 3이라면 “abc”라는 문자열이 반복되는지를 확인해야함
그렇다면 먼저, “abc”라는 문자열의 길이 3을 cnt에 더해놓고 시작한다.
그리고 “abc”가 1보다 많이 반복된다면 → 해당 반복된 개수 정수를 → 문자열로 변환하여 → 이 문자열의 길이만큼을 cnt에 더해주는 방식인 것.
class Solution {
/*
문자열을 1개 이상의 단위로 잘라 압축하려 한다
1개 이상의 단위로 문자열을 잘라 압축하여 표현한 문자열 중, "가장 짧은 것의 길이" 를 리턴
---
이해
ababcdcdababcdcd --> (2개단위 ) :2ab2cd2ab2cd , (8개단위)2ababcdcd ( 이게 가장 짧게 압축 가능)
n개 단위로 자르고 -> 마지막에 남는 문자열 -> 그대로 붙여주면 된다.
---
방법
- 단위의 경우의 수 : 1개 ~ s.length() -> s는 최대 1000 이기에, 최대 1000 가지 단위가 나옴
- 만약 단위를 : n 으로 하면 -> 이 문제의 경우는 check하는 위치가 : i , i+n,i+2n,... 이런식 이 된다.
- 즉, 하나의 단위에 대해 최대 O(n) 만큼을 반복
- 브루트 포스로 풀더라도 O(n^2)
- 반복문을 돌면서, pre 위치에서의 문자열, 현재 위치에서의 문자열 , pre문자열이 반복된 횟수 를 저장한다.
-------
문제점
- String을 매번 생성?? 어차피 동등 비교를 할 때 -> 내부 데이터 값을 비교하는 것이기 때문에..
- 이전 문자열을 저장해두지 않고, 이전 위치를 저장해 두고, 비교하는게 좋을 듯
*/
public int solution(String s) {
int answer = Integer.MAX_VALUE;
// 문자열의 길이
int len = s.length();
int temp = 0;
// 단위
for(int u = 1; u <= len; u++){
answer = Math.min(answer,solve(u,s));
}
return answer;
}
// 이전 위치 ,현재 위치, unit 크기
// [ pre..pre+u-1] 과 [cur..cur+u-1]이 동일한지 확인하는 로직
public boolean equal(int pre,int cur,int u,String s){
// pre .. pre + u - 1
// cur .. cur + u - 1
for(int i=0;i<u;i++){
if(s.charAt(pre+i) != s.charAt(cur+i) ) return false;
}
return true;
}
// ucnt라는 정수의 자리수를 리턴
public int intlen(int ucnt){
int temp = ucnt;
int len = 0;
while(temp/10 != 0 ){
len++;
temp %= 10;
}
len++;
return len;
}
// 해당 unit 크기로 문자열을 잘라가며 확인하는 경우, 압축된 문자열의 길이를 구한다
public int solve(int u, String s){
// System.out.println("========== unit : "+u+" ==================");
int len = s.length();
int pre = 0, cur = 0;
int ucnt = 1, cnt = 0; // ucnt는 이전문자열과 동일한 문자열의 개수(연속한경우만)
// cnt는 압축된 문자열의 길이
if(cur + u < len){
// 현재 자른 문자열 길이
cnt += u;
// 다음 시작 위치
cur += u;
while( cur + u <= len){
// 비교 -> 동일한경우, ucnt를 1 증가시킨다.
if(equal(pre,cur,u,s)){
ucnt++;
}else{
// 동일하지 않은 경우
if (ucnt > 1 ) {
cnt += intlen(ucnt);
}
// 즉 cur 문자열은 이제, 새로운 pre문자열이 될 거라
// cnt 에 u 를 더해준다. ucnt는 1로 초기화시킨다.
cnt += u;
ucnt = 1;
}
pre = cur;
cur += u;
}
if(ucnt>1){
cnt += intlen(ucnt);
}
}
// 남은 부분들을 더한다
cnt += (len-cur);
return cnt;
}
}테스트 1 〉 통과 (0.06ms, 72.2MB)
테스트 2 〉 통과 (0.37ms, 77.8MB)
테스트 3 〉 통과 (0.15ms, 75.3MB)
테스트 4 〉 통과 (0.07ms, 71.3MB)
테스트 5 〉 통과 (0.02ms, 79MB)
테스트 6 〉 통과 (0.07ms, 72.2MB)
테스트 7 〉 통과 (0.28ms, 76MB)
테스트 8 〉 통과 (0.46ms, 70.9MB)
테스트 9 〉 통과 (0.52ms, 71.9MB)
테스트 10 〉 통과 (1.51ms, 73.2MB)
테스트 11 〉 통과 (0.06ms, 73.3MB)
테스트 12 〉 통과 (0.09ms, 71.7MB)
테스트 13 〉 통과 (0.08ms, 75.4MB)
테스트 14 〉 통과 (0.51ms, 70.5MB)
테스트 15 〉 통과 (0.09ms, 75.9MB)
테스트 16 〉 통과 (0.03ms, 76.9MB)
테스트 17 〉 통과 (0.82ms, 71.5MB)
테스트 18 〉 통과 (0.49ms, 76.3MB)
테스트 19 〉 통과 (0.40ms, 72.4MB)
테스트 20 〉 통과 (0.98ms, 73.5MB)
테스트 21 〉 통과 (1.21ms, 75MB)
테스트 22 〉 통과 (0.87ms, 76.8MB)
테스트 23 〉 통과 (0.89ms, 76.5MB)
테스트 24 〉 통과 (0.78ms, 76.5MB)
테스트 25 〉 통과 (0.80ms, 71.8MB)
테스트 26 〉 통과 (0.90ms, 74.6MB)
테스트 27 〉 통과 (1.30ms, 75.1MB)
테스트 28 〉 통과 (0.03ms, 74.7MB)