[프로그래머스] 2020 카카오 #1 문자열 압축 (Java)

#1 문자열 압축

난이도 : LEVEL 2

유형 : 문자열

코딩테스트 연습 - 문자열 압축

▸ 문제

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

▸ 제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

 

문제 풀이  

처음에 설계하는데 생각보다 시간이 걸렸다. 문자열을 다루는 문제는 웬만하면 재귀로 풀지 않으려고하는 습성이 있어서 반복문으로 접근했다. 그러다보니 pattern이 되는 문자열을 어떻게 갱신해주고 반복문을 돌려야하는지 고민이 필요했다.

 

구상

문제 이해도 자체는 간단하다. 그냥 연속되는 동일한 문자들을 압축시켜주면 된다. 그런데 문제는 문자열을 다루다가 자칫하면 로직이 무거워질 수 있기 때문에 가볍게 접근하려고 고민하다가 지금 내가 PS를 하고 있다는 것을 깨닫고 무작정 풀이에 들어갔다.

 

첫 번째로 고려해야 할 문제는 pattern 문자열을 구하는 것이다. 이는 문자열 s에서 직접 하나씩 뽑아줘야 한다. pattern의 길이는 (1~s 길이/2)를 넘을 수 없다는 것을 인지해야 한다. 

 

두 번째로 pattern을 구했으면 이제 전체의 문자열에 순차적으로 pattern을 들이밀어 중복이 되는 수를 카운트해주며 일치하지 않을 때 까지 탐색해주면 된다. 연속되는 것만 허용되기 때문에 일치하지 않으면 바로 넘어가면 된다. 그리고 여기서 현재 카운트한 정보들을 저장하기 위해서 새롭게 String문자열을 정의해줘야 한다.

 

세 번째로는 두 번째의 과정이 끝나고 다음 탐색으로 넘어가는 부분이다. 여기서는 이전에 사용한 변수들을 갱신해주자. 위에서 사용한 더이상 pattern, 카운트 해준 수들은 필요없다.

 

 

설계

1. r의 길이만큼의 pattern을 구해준다. s.substring(0,r);
   1. r의 길이는 [1, s의 길이 /2]의 범위를 가진다.
2. pattern의 다음 문자열부터 순차적으로 탐색하여 연속되는 데이터를 찾는다.
   1. 탐색의 범위는 i: [r, s의 길이-r]로, 매 증가는 i+=r이다.
   2. 연속되는 문자열을 카운트해준다. if(pattern.equals(s.substring(i,i+r)))
   3. 연속이 끊기는 부분에서 해당 탐색한 문자열들의 정보(reStr)를 저장한다. ex) aa > 2a
3. 이렇게 모든 문자열들의 압축 정보(reStr)을 구해 최솟값을 출력해준다.

 

풀이 코드 (문자열)

class Solution {
    public int solution(String s) {
         int answer = Integer.MAX_VALUE;
        int len = s.length();
        
        if(s.length()==1) return 1;
        
        for(int r=1; r<=len/2; r++) {
        	String pattern  = s.substring(0,r);
        	int compLen =0;
        	int cnt =1;
        	String reStr="";
        	for(int i=r; i<=s.length()-r; i+=r){
        		if(pattern.equals(s.substring(i,i+r))){
    				cnt++;
    			}else {
    				if(cnt>1) {
    					reStr += cnt+"";
    				}
   				    reStr += pattern;
    				pattern = s.substring(i,i+r);
    				cnt=1;
    			}
        	}
        	
        	if(cnt>1) {
    			reStr+= ""+cnt;
    		}
    		reStr+= pattern;
    		
    		int div = s.length()%r;
    		answer = Math.min(answer, reStr.length()+div);
        }
        return answer;
    }
}

 

풀이 코드 (정수형)

문제는 압축된 문자열의 최소 길이를 물어보고 있다. 그래서 사실상 컴퓨터는 무거운 문자열에 대한 정보를 몰라도 된다. 그래서 위의 문자열 풀이에서 길이에 대한 정보로만 바꿔서 다시 풀었다. 

 

(int)Math.log10(cnt)를 사용한 이유는 자릿수를 세기위해서이다. 예로 연속되는 문자의 수가 1~9일 경우는 1a, 2a, ... , 9a 이렇게 저장되기 때문에 1로 카운트 해주고 그 외에 10,100의 연속되는 수는 2, 3개의 길이로 카운트 해줘야하기 때문이다.

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        int len = s.length();
        
        if(s.length()==1) return 1;
        for(int r=1; r<=len/2; r++) {
        	String pattern  = s.substring(0,r);
        	int compLen =0;
        	int cnt =1;
        	for(int i=r; i<=s.length()-r; i+=r){
        		if(pattern.equals(s.substring(i,i+r))){
    				cnt++;
    			}else {
    				if(cnt>1) {
    					compLen += (int)Math.log10(cnt)+1;
    				}
    				pattern = s.substring(i,i+r);
    				compLen += pattern.length();
    				cnt=1;
    			}
        	}
        	
        	if(cnt>1) {
    			compLen += (int)Math.log10(cnt)+1;
    		}
    		
    		int div = s.length()%r;
    		if(div>0) compLen += div;
    		compLen += pattern.length();
    		
    		answer = Math.min(answer, compLen);
        }
        
        System.out.println(answer);
        return answer;
    }
}

 

로직에서 문자열로 데이터를 다루는 것과 정수형으로 다루는 것의 성능 차이는 아래의 결과를 보면 알 수 있다.

 

(왼)String 풀이, (오른)정수형 풀이