[프로그래머스] 문자열 압축

[프로그래머스] level2 문자열 압축

 

소요시간 : 42분

 

map 으로 삽질하다가 오래 걸린 문제.. ㅋ

절대 40분씩이나 걸릴 만한 문제는 아닌 듯

 

자르는 단위를 1부터 단어길이의 반까지 모두 시도해본다.

단어 길이의 반 초과 부터는 어차피 압축필요없이 문자열길이와 압축길이가 같으므로 시도하지 않는다.

자르는 단위대로 cur 과 next를 갱신하는데,

cur과 next가 같으면 계속 count를 올려서 같은 문자열이 몇 번 나왔는지 체크한다.

cur과 next가 다르면 StringBuilder에 append 후 cur에 next를 담아 비교대상을 바꿔주고 ,  count = 1로 초기화한다.

이걸 문자열 끝까지 확인하여 StringBuilder 길이로 MIN 을 갱신한다.

class Solution {
  public int solution(String s) {
    for (int len = 1; len < s.length(); len++) {
    	cut(len, s);
    }
    if(MIN > s.length()) MIN = s.length();
    return MIN;
  }

  int MIN = Integer.MAX_VALUE;
  public void cut(int len, String s) {
    StringBuilder sb = new StringBuilder();
    String cur = s.substring(0, len);
    String next;
    int count = 1;
    for (int i = len; i < s.length(); i+=len) {
      if(i+len <= s.length()) next = s.substring(i, i+len);
      else next = s.substring(i);

      if(cur.equals(next)) {
          count++;
      }
      else {
        if(count > 1) sb.append(count).append(cur);
        else sb.append(cur);

        cur = next;
        count = 1;
      }
    }
    if(count > 1) sb.append(count).append(cur);
    else sb.append(cur);

    if(MIN > sb.length()) MIN = sb.length();
  }
}