프로그래머스 lv2 문자열 압축

문제 링크

문자열 압축

풀이

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        int cuttingRange = 1;
        for (int i = 0; i < s.length() / 2 + 1; i++) {
            Stack<String> stack = new Stack<>();
            StringBuilder resultString = new StringBuilder();
            StringBuilder slicedString = new StringBuilder();
            int cnt = 0; // 잘라내고 싶은 길이만큼 for 문을 돌았는지 확인하기 위한 변수
            char[] chars = s.toCharArray();
            for (int j = 0; j < s.length(); j++) {
                
                slicedString.append(chars[j]);
                cnt++;
                
                if (cnt == cuttingRange) {
                    if (stack.isEmpty() || stack.peek().equals(slicedString.toString())) {
                        stack.push(slicedString.toString());
                    } else {
                        int size = stack.size();
                        if (size > 1) {
                            resultString.append(size).append(stack.pop());
                        } else {
                            resultString.append(stack.pop());
                        }
                        // 로직이 끝났으면 비우고, 현재 갖고 있는 변수를 스택에 더한다.
                        stack.clear();
                        stack.push(slicedString.toString());
                    }
                    // 잘라내는 변수에 대해서는 초기화한다.
                    cnt = 0;
                    slicedString = new StringBuilder();
                }

                if (j == s.length() - 1) {
                    // for 문이 끝났지만, 아직 비우지 못한 stack 을 위해서. 
                    int size = stack.size();
                    if (size > 1) {
                        resultString.append(size).append(stack.pop());
                    } else {
                        resultString.append(stack.pop());
                    }
                    // cuttingRange 가 커지면 커질수록, stack 에도 못들어가는 문자열이 발생하기에, 그런 문자열들은 다 더해준다.
                    if (slicedString.length() > 0) resultString.append(slicedString);
                }
            }
            answer = Math.min(answer, resultString.length());
            cuttingRange++; // 잘라내는 길이를 늘린다.
        }
        return answer;
    }
}

소감

• 첫 lv2의 문제. 풀긴 풀었다만 코드가 아주 지저분 한 것 같다.

• 너무 라이브러리에 의존하는거 아닌가? 라는 생각이 들었다. 다음 문제는 최대한 사용하지 않고 풀어보도록 하자.

• 다른 사람의 풀이를 보면 DP로 풀었고, 라이브러리는 사용하지 않았다. 보고 참고하자.

  class Solution {
      public int solution(String s) {
          int answer = 0;
  
          for(int i=1; i<=(s.length()/2)+1; i++){
              int result = getSplitedLength(s, i, 1).length();
              answer = i==1 ? result : (answer>result?result:answer);
          }
  
          return answer;
      }
  
      public String getSplitedLength(String s, int n, int repeat){
          if(s.length() < n) return s;
          String result = "";
          String preString = s.substring(0, n);
          String postString = s.substring(n, s.length());
  
          // 불일치 -> 현재까지 [반복횟수 + 반복문자] 조합
          if(!postString.startsWith(preString)){
              if(repeat ==1) return result += preString + getSplitedLength(postString, n, 1);
              return result += Integer.toString(repeat) + preString + getSplitedLength(postString, n, 1);
          }
  
          return result += getSplitedLength(postString, n, repeat+1);
      }
  }