문자열 압축 알고리즘

anonymous·2022년 6월 18일
0

생각에도 루프가 있다

문자열 압축 알고리즘 구현

  • 입력: 문자열
  • 출력: 문자열 압축해서 표현한 문자열 중 가장 짧은 길이

조건

1 반복되는 문자에 대해선 숫자로 대체 가능.
2 압축시 순서는 유지해야함.
3 문자열은 제일 앞에서부터 정해진 단위로 자를 수 있음 (중간부터 잘라서 사용할 수 없다)
예) xababcdcdababacdcd 인 경우 ababcdcd를 2ababcdcd 못함

입출력 예제)

단위 패턴의 의미

맞고
1순차적 패턴 char X 횟수
XOR
2순차적 패턴 char X 횟수
XOR
3순차적 패턴 char X 횟수
->
틀리고
1순차적 패턴 char X 횟수
AND
2순차적 패턴 char X 횟수
AND
3순차적 패턴 char X 횟수

키워드

  • 현재 문자열 패턴
  • 이전 문자열 패턴
  • 패턴 카운터
  • 실 가위
  • 루프

draw


psudocode

  1. 패턴 길이로 잘린 문자열 패턴을 이전 패턴 (단위)값과 비교한다.

  • 조건 1 : 일치
    2. 이전 패턴 값이랑 일치하면 패턴 횟수를 카운트한다.

  • 조건 2 : 불일치
    3. 일치하지 않는다면 이전 패턴 횟수 카운트를 String 변환 후 길이만큼 문자열 길이에 더한다. / 패턴 카운트를 초기화한다. 이전 패턴 값을 패턴 길이로 잘린 문자열로 교체한다

  1. 해당 패턴 길이의 반복문이 종료되면 이전 패턴 횟수 카운트를 String 변환 후 길이만큼 문자열 길이에 더한다.
  1. 해당 패턴 길이로 나눠진 경우가 가장 짧다면 answer를 갱신한다.

layered psudocode

def solution(s):
	if len(s) == 1:
		return 1
	
	result = ""
	length = []
	cut = 1

for i in range(1, len(s)//2+1):
	cnt = 1 # 패턴 횟수
1. 패턴 길이로 잘린 문자열 패턴을 이전 패턴 (단위)값과 비교한다.
	temp_str = s[:i] # 문자열 길이 
	for j in range(i, len(s), i):
	print(s[j:j+i]) # 패턴 길이 

조건 1 : 일치
	2. 이전 패턴 값이랑 일치하면 패턴 횟수를 카운트한다.
		if temp_str == s[j:j+i]:
			cnt += 1

조건 2 : 불일치
	3. 일치하지 않는다면 이전 패턴 횟수 카운트를 String 변환 후 길이만큼 문자열 길이에 더한다. / 패턴 카운트를 초기화한다. 이전 패턴 값을 패턴 길이로 잘린 문자열로 교체한다
		else:
			if cnt == 1: 
				cnt = ""
			result += str(cnt) + temp_str 
			cnt = 1 
			temp_str = s[j:j+i] 
	if cnt ==1:
		cnt = ""
		
4. 해당 패턴 길이의 반복문이 종료되면 이전 패턴 횟수 카운트를 String 변환 후 길이만큼 문자열 길이에 더한다.
	result += str(cnt) + temp_str 
	length.append(len(result)) 
	result = "" 
	
return min(length)

sol

Python 풀이

# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
def solution(s):
    # 예외 처리 
    if len(s) == 1:
        return 1
    
    result = ""
    length = []
    cut = 1
    
    # // = 나누기 후 소수점 버리기 
    # 포인터 1 : 순서 0
    for i in range(1,len(s)//2+1):
        cnt = 1
        # 문자열 임시 짜르기 (초반 절반)
        temp_str = s[:i]
        print('----------')
        print(temp_str)
        
        # 포인터 2 : 순서 +i
        for j in range(i,len(s),i):
            print('j : '+s[j:j+i])
            if temp_str == s[j:j+i]:
                cnt += 1
            else:
                if cnt == 1:
                    cnt = ""
                # 압축 숫자 + 좌측 문자열
                result += str(cnt) + temp_str
                cnt = 1
                temp_str = s[j:j+i]
        if cnt == 1:
            cnt = ""
        
        # 압축 숫자 + 포인터 1 || 포인터 2 결과값 
        result += str(cnt) + temp_str
        print('zip : '+result)
        length.append(len(result))
        result = ""
    print(length)
    return min(length)
# TEST CASE
# aabbaccc
# ababcdcdababcdcd
print(solution("aabbaccc"))

print

JS 풀이

function solution(s) {
    let min = 2000;
    var count = 0;
    
    //* 길이가 1인 경우
    if(s.length==1){
        return 1;
    }
    
    //자르는 길이
    for(let i =1 ; i< s.length; i++){
        let tempLen = s.length;
        //* 패턴 길이 최초 값 = 1
        let patternUnit = 1;
        let pattern = "";
        
        //전체 길이 / 자르는 길이만큼 반복
        for (let j = 0; j< Math.floor(s.length / i); j++){
        //인덱스 = j * i
            let index = j * i;
            
            //인덱스~인덱스 + 자르는 길이까지 이전 패턴과 비교
            if(s.substring(index, index + i) === pattern){
                //패턴이 일치한다면 길이 - i
                tempLen -= i;
                //패턴 카운트를 기록하기 위함)
                patternUnit++;
            }else{
                //패턴이 불일치한다면
                //패턴 카운트를 초기화하고 더한다.
                if(patternUnit > 1){
                    tempLen += String(patternUnit).length;
                    patternUnit = 1;
                }
                //현재 패턴을 기록
                pattern = s.substring(index, index + i);                
            }        
    }
    //모든 반복이 종료되면
    //패턴 횟수를 더 해준다.
        if(patternUnit > 1){
            tempLen += String(patternUnit).length;
        }
    //tempLen이 min보다 작다면 min = tempLen, answer = i
        if(tempLen < min){
            min = tempLen;
            count = i;
        }
    }
    return min;
}

Java 풀이

public class Main {
    public static void main (String[] args) {
        Main main = new Main();
        System.out.println(main.solution("2a2ba3c"));
    }
    public int solution(String s) {
        int answer = s.length();
        
        for (int i = 1; i <= s.length() / 2; i++) {
            String comp = compression(s, i);
            int compLen = comp.length();
            answer = Math.min(answer, compLen);
        }
        return answer;
    }
    
    /**
    * 문자열 압축
    */
    private String compression(String s, int i) {
        String compResStr = ""; // 압축 결과
        int compCount = 1;   // 압축 횟수
        String compStr = "";    // 비교 대상
        String currentStr = ""; // 기준 문자열
        
        Boolean changeCur = true;  // 기준 문자열을 변경할 것인지
        Boolean changeComp = true;  // 마지막인지 구분
        
        for (int j = 0; j <= s.length() - i; j += i) {
            // 기준 문자열 생성
            if (changeCur) {
                currentStr = s.substring(j, j + i);
            }
            // 비교 대상 생성
            // 마지막 비교인 경우
            if (j + i + i >= s.length()) {
                compStr = s.substring(j + i);
                // 마지막이라는 의미 어차피 밑에서 다르다는 판별이 남
                if (compStr.length() < currentStr.length()) {
                    currentStr += compStr;
                }
            } else {
                compStr = s.substring(j + i, j + i + i);
            }
                
            if (currentStr.equals(compStr)) {
                changeCur = false;   // 기준 문자열 그대로 유지
                compCount++;
            } else {
                changeCur = true;
                compResStr += compCount > 1 ? compCount + currentStr : currentStr;
                compCount = 1;
            }
            
            compStr = "";
        }
        return compResStr;
    }
}

C 풀이

#include <string>

using namespace std;

int solution(string s) {
    int answer = s.size();
    for(int i=1; i<=s.size()/2; i++){
        int cnt = 1;
        string temp = "", a = "";
        a = s.substr(0,i);
        for(int j=i; j<s.size(); j+=i){
            if(a==s.substr(j,i)) cnt++;
            else{
                if(cnt>1) temp+= to_string(cnt);
                temp += a;
                a=s.substr(j,i);
                cnt = 1;
            }
        }
        if(cnt>1) temp+=to_string(cnt);
        temp+=a;
        if(answer>temp.size()) answer = temp.size();
    }
    return answer;
}

풀이 노가다

s = 'aabbcc'
def solution(s):
    # 예외 처리 

    # len(s) = aabbcc
    if len(s) == 1: 
        return 1
    
    result = ""
    length = []
    cut = 1
    
    # // = 나누기 후 소수점 버리기 
    # 포인터 1 : 순서 0

    # if i = 1
    for i in range(1,len(s)//2+1): # len(s)//2+1 = 6 // 2 + 1 -> 4
        cnt = 1
        # 문자열 임시 짜르기 (초반 절반)
        temp_str = s[:i] #  s[:i] = aabbcc[:1] = a 
        print('----------')
        print(temp_str) # a 
        
        # 포인터 2 : 순서 +i

        # if j = 1
        # for 1 in range( 1, 6, 1):	
        #  print('j : '+s[j:j+i]) #  s[j:j+i] = aabbcc[1:1+1] = a 
        # if temp_str == s[j:j+i]: # a == a
        #        cnt += 1 # cnt = 2 
        
        # if j = 2
        # for 1 in range( 1, 6, 1):	
        #  print('j : '+s[j:j+i]) #  s[j:j+i] = aabbcc[2:2+1] = b 
        # if temp_str == s[j:j+i]: # a == b
        #        cnt += 1
        # else:
        #        if cnt == 1:
        #            cnt = ""
                # 압축 숫자 + 좌측 문자열
        #        result += str(cnt) + temp_str # str(cnt) = 2 + a -> result = 2a 
        #        cnt = 1
        #        temp_str = s[j:j+i] # temp_str = b 

        # if j = 3
                # for 1 in range( 2, 6, 1):	
        #  print('j : '+s[j:j+i]) #  s[j:j+i] = aabbcc[3:3+1] = b 
        # if temp_str == s[j:j+i]: # b == b
        #        cnt += 1

        # if j = 4
        # for 1 in range( 1, 6, 1):	
        #  print('j : '+s[j:j+i]) #  s[j:j+i] = aabbcc[4:4+1] = c
        # if temp_str == s[j:j+i]: # b == c
        #        cnt += 1
        # else:
        #        if cnt == 1:
        #            cnt = ""
                # 압축 숫자 + 좌측 문자열
        #        result += str(cnt) + temp_str # str(cnt) = 2 + b -> result = 2a2b 
        #        cnt = 1
        #        temp_str = s[j:j+i] # temp_str = c



        for j in range(i,len(s),i): 
            print('j : '+s[j:j+i]) #  s[j:j+i] = aabbcc[1:1+1] = a 
            if temp_str == s[j:j+i]: # a == a
                cnt += 1
            else:
                if cnt == 1:
                    cnt = ""
                # 압축 숫자 + 좌측 문자열
                result += str(cnt) + temp_str
                cnt = 1
                temp_str = s[j:j+i]
        if cnt == 1:
            cnt = ""
        
        # 압축 숫자 + 포인터 1 || 포인터 2 결과값 
        result += str(cnt) + temp_str
        print('zip : '+result)
        length.append(len(result))
        result = ""
    print(length)
    return min(length)

출처

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

https://mungto.tistory.com/12

https://astrid-dm.tistory.com/360

https://muhly.tistory.com/130

https://woojeenow.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%95%95%EC%B6%95-ckotlin

profile
anonymous
기술블로거입니다
이전 포스트

build tool-gradle-part1

다음 포스트

Project Structure-package-by-feature-vs-layer

0개의 댓글