[level2] 문자열 압축 JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

 

문자열을 1, 2 ~ 개 단위로 쪼개어 같은 단어들을 압축하는 방식으로 진행했을때 압축 후 문자열의 길이가 제일 적은 것을 리턴하는 문제이다.  간단한 문제라고 생각하고 풀었는데,, 결과는 ㅜㅜ

class Solution {
    static int answer = Integer.MAX_VALUE;
	public int solution(String s) {
	
		int n = s.length();
		
		if(n == 1) return 1;
		
	    for(int i = 1; i <= n/2; i++) {
	    	dfs(s, i);
	    }
	    
	    System.out.println(answer);
		return answer;
	}
	
	private void dfs(String s, int n) {
		 
		String str = s.substring(0, n);
		int len = n;
		int cnt = 0;
		
		s = s.substring(n);
		
		while(s.length() >= n) {
			String tmp = s.substring(0, n);
			if(str.equals(tmp)) {
				if(cnt == 0) { 
					cnt++; len +=1; 
				}
			} else {
				cnt = 0;
				str = tmp;
				len += n;
			}
            
            if(len >= answer) return;
			s = s.substring(n);
		}
		
		
		if(s.length() > 0) len+= s.length();
		
		answer = Math.min(len, answer);
	}
}

* 문제가 쉽다고 느껴질 수록 정확성을 놓치는 것 같다..

 

- 다시 한 번 문제를 살펴 봤을 때,, 발견한 나의 오류

바로 나는 숫자에는 len+=1 로 길이를 추가했던것!!!

숫자 자릿수로 길이를 추가하니 성공~!! 문제는 늘 꼼꼼하게 풀자~!

** len += (int)(Math.log10(cnt)+1); ** 

 

[최종 답안]

class Solution {
   static int answer = Integer.MAX_VALUE;
	public int solution(String s) {
	
		int n = s.length();
		
		if(n == 1) return 1;
		
	    for(int i = 1; i <= n/2+1; i++) {
	    	dfs(s, i);
	    }
	    
	    System.out.println(answer);
		return answer;
	}
	
	private void dfs(String s, int n) {
		 
		String str = s.substring(0, n);
		int len = n;
		int cnt = 1;
		
		s = s.substring(n);
		
		while(s.length() >= n) {
			String tmp = s.substring(0, n);
			if(str.equals(tmp)) {
				cnt++;
			} else {
				if(cnt > 1) {
					len += (int)(Math.log10(cnt)+1);
				}
				cnt = 1;
				str = tmp;
				len += n;
			}
            
            if(len >= answer) return;
			s = s.substring(n);
		}
		
		if(cnt > 1) len += (int)(Math.log10(cnt)+1);
		
		System.out.println(s.length());
		if(s.length() > 0) len+= s.length();
		
		answer = Math.min(len, answer);
	}
}