Lv2-문자열 압축

---

0. 문제

문자열이 하나 주어질 때, 중복되는 문자를 압축하려고 한다.
그 압축의 예시는 다음과 같다.

• aabbcc ==> 2a2b2c
• abcabcc ==> 2abcc

하지만 두번째 예시는 다음과 같이 압축 가능하다.

• abcabcc ==> abcab2c

두 경우의 압축 길이는 각각 5와 7로, 첫번째가 더 짧다.

문제) 문자열이 하나 주어졌을 때, 압축 길이가 가장 짧은 것의 길이를 구하여라.

(자세한 설명은 여기서)(https://programmers.co.kr/learn/courses/30/lessons/60057)

---

1. 풀이

import java.util.*;

class Solution {
    static int compress(int len, String s) {
        int count = 1;
        String current = "";
        String next = "";
        StringBuilder answer = new StringBuilder();
        
        // 길이만큼 반복함
        for(int i=0; i<=s.length()/len; i++) {
            int start = i*len;
            int end = (i+1)*len>s.length() ? s.length() : (i+1)*len;
            // 현재 문자열
            current = next;
            // 비교할 다음 문자열
            next = s.substring(start, end);
            
            // 같으면 중복 횟수 추가
            if(current.equals(next)) {
                count++;
            }
            // 다르면 중복된 횟수만큼 압축
            else {
                if(count>1) {
                    answer.append(count + current);
                    count = 1;
                }
                else {
                    answer.append(current);
                }
            }
        }
        
        if(count>1) {
            answer.append(count + next);
        }
        else {
            answer.append(next);
        }
        return answer.length();
    }
    
    public int solution(String s) {
        ArrayList<Integer> answerList = new ArrayList<>();
        // 길이가 1이면 그냥 반환
        if(s.length()==1) {
            return 1;
        }
        
        // 압축 과정
        for(int len=1; len<=s.length()/2; len++) {
            answerList.add(compress(len, s));
        }
        
        //정렬 후 반환
        Collections.sort(answerList);
        return answerList.get(0);
    }
}

---

2. 설명

압축 과정까지 main에 작성하면 길어질 것 같아, 메소드로 작성하였다.

압축 과정은 다음과 같다.
주어진 길이 len만큼 substring하여 current와 next를 만들고 비교하게 하였다.

---

• current와 next 만들기

  substring의 시작점과 끝점을 각각 start와 end로 정의하며,
  start는 len의 배수이고, end 또한 len만큼 더해지므로 len의 배수이다.

// 시작점, 끝점 정의
int start = i*len;
int end = (i+1)*len>s.length() ? s.length() : (i+1)*len;
// 현재 문자열
current = next;
// 비교할 다음 문자열
next = s.substring(start, end);

---

• 중복 압축 처리

  그리고 같을 시에는 중복이므로 count++하고,
  중복이 끝난 else에서 count와 함께 압축 처리하였다.

// 같으면 중복 횟수 추가
if(current.equals(next)) {
    count++;
}
// 다르면 중복된 횟수만큼 압축
else {
    if(count>1) {
        answer.append(count + current);
        count = 1;
    }
    // 중복이 없다면 그냥 붙임
    else {
        answer.append(current);
    }
}

---

• 마지막 next 처리

  그리고 문자열 길이가 len의 배수가 아닐수도 있다.
  (문자열 길이: 7, len=2)
  이렇게 되면, 마지막 next의 end는 4*len=8이 되어
  index 초과 오류가 나게 된다.
  따라서 "end>문자열 길이"가 될 경우, 그냥 문자열 끝을 가리키도록 처리한다.

// 문자열 길이를 초과하면, 끝을 가리키도록 처리
int end = (i+1)*len>s.length() ? s.length() : (i+1)*len;

---

• 정렬

  compress()값을 List로 받아서 정렬 후에, 가장 작은 첫번째 원소를 반환하였다.

// List로 값을 받음
for(int len=1; len<=s.length()/2; len++) {
    answerList.add(compress(len, s));
}
        
//정렬 후 반환
Collections.sort(answerList);
return answerList.get(0);

---

3. 느낀 점

문제를 푸는 아이디어는 금방 떠올랐으나

• current와 next를 작성하는 과정에서 코드가 꼬임
• 마지막 next의 end를 확인하지 않아 index 초과 오류가 남
• 길이가 1인 문자열의 처리도 제대로 하지 않음

위 3가지 이유로 많은 시간이 걸렸다ㅠㅜ

반복, 특히나 재귀적 과정(next가 current가 되는)이 있는 코드는 전체 과정을 적어보며 반복되는 관계를 정확히 찾아내는 것이 중요하다.

또한 반복문은 항상 끝부분이 중요하다.
중간 부분이 잘 된다고 넘기지 말고, 반드시 끝까지 신경써줘야 한다.

마지막으로 문제를 잘 파악하여 입력값 처리를 할 것.
대부분 공백이나 입력값이 하나일 때, 혹은 전체일 때 등을 처리하면 된다.

---

추가

테스트를 돌리는데 수행 시간이 상당히 길었다.
(30~40ms를 왔다갔다했다ㄷㄷ)

아마 값을 List로 받고, 정렬까지 돌려서 그런듯 하다.
게다가 compress() 내부에 count 처리하는 if-else문도 중복되어 깔끔하지 않다.

이런 점을 보완하여 깔끔하고 시간도 단축시킬 것이다.