[알고리즘 / 프로그래머스] 문자열 압축

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

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

 

문제는 위와 같으며, 이 문제는 문자를 1개씩 반복하는 경우, 2개씩 반복하는 경우, ... n개씩 반복하는 경우를 순차적으로 모두 확인하면서 기준 문자와 다음 문자가 같은 경우 수를 증가시키고 다른 경우는 지금까지 구한 기준 문자와 그 수를 저장한 뒤 기준 문자를 다음 문자로 변경하는 방식으로 모든 반복 경우를 확인한 뒤, 그때마다 구해진 문자열의 길이를 비교해 최소 길이를 출력하는 방식으로 문제를 해결하였습니다.

 

파이썬 코드는 다음과 같습니다.

def solution(s):
    answer = 1  # 문자열의 길이가 1인 경우에는 1이 그냥 출력되어야 하므로 초기값을 1로 지정
    
    # 문자열을 1부터 문자열 길이의 절반까지 반복할 수 있으므로 순서대로 반복
    for n in range(1, len(s) // 2 + 1):
        now = ""  # 현재 기준 문자
        count = 0  # 기준 문자의 수
        strings = []  # n개 길이로 나누어진 문자를 담을 배열

		# n개 길이로 문자 나누기
        start = 0
        end = start + n
        while end < len(s):
            strings.append(s[start:end])
            start = end
            end = start + n
        strings.append(s[start:])  # 길이가 n개보다 작게 남은 나머지 문자 추가

        temp = ""  # 압축된 문자열

        for cs in strings:
            if now == "":  # 처음 문자인 경우
                now = cs  # 기준문자로 추가하고
                count += 1  # 수 ++
            else:
                if now == cs:  # 기준 문자와 현재 문자가 같은 경우
                    count += 1  # 수 ++
                else:  # 기준 문자와 현재 문자가 다른 경우
                    if count <= 1:  # 기준 문자 수가 1개 이하인 경우
                        temp += "{}".format(now)  # 문자만 추가
                    else:  # 기준 문자 수가 2개 이상인 경우
                        temp += "{}{}".format(count, now)  # 기준문자 수와 기준 문자를 추가
                    now = cs  # 현재 문자를 기준문자로 변경
                    count = 1  # 기준 문자 수 초기화

		# 남은 문자 압축 문자열에 추가
        if count <= 1:
            temp += "{}".format(now)
        else:
            temp += "{}{}".format(count, now)

        if answer == 1:  # 처음으로 압축된 문자인 경우
            answer = len(temp)  # 압축 문자 길이 저장
        else:
            answer = min(answer, len(temp))  # 기존 압축 문자 길이와 현재 압축 문자 길이 중 작은 값 저장

    return answer

 

자바 코드는 다음과 같습니다.

import java.util.ArrayList;

class Solution {
    public int solution(String s) {
        int answer = 1;
        
        // 문자를 1개씩 잘라서 비교하는 경우부터 총 문자열 길이의 절반만큼 잘라 비교하는 경우까지 반복
        for (int n = 1; n <= s.length() / 2; n++) {
            String now = "";  // 기준 문자열
            int count = 0;    // 기준 문자열의 개수

			// n 개씩 문자열 분리하기
            ArrayList<String> strings = new ArrayList<>();  // n 개씩 잘려진 문자열 저장
            int start = 0;
            int end = start + n;
            while(end < s.length()) {
                strings.add(s.substring(start, end));
                start = end;
                end = start + n;
            }
            strings.add(s.substring(start));  // 길이가 n보다 작아서 남은 문자열 추가 저장

            StringBuilder sb = new StringBuilder();  // 압축 문자열

            for(String currentStr : strings) {
                if (now.equals("")) {  // 처음 문자열인 경우
                    now = currentStr;  // 기준 문자열로 추가
                    count++;   // 기준 문자열 수 증가
                    continue;
                }

                if (now.equals(currentStr)) {  // 기준 문자열과 현재 문자열이 같은 경우
                    count++;  // 기준 문자열 수 증가
                } else {  // 기준 문자열과 현재 문자열이 다른 경우
                    if (count <= 1) {  // 기준 문자열의 수가 1이하인 경우
                        sb.append(now);  // 문자열만 압축 문자열에 추가
                    } else {  // 기준 문자열의 수가 2이상인 경우
                        sb.append(count).append(now);  // 기준 문자열의 수와 기준 문자열을 압축 문자열에 추가
                    }
                    now = currentStr;  // 현재 문자열을 기준 문자열로 저장
                    count = 1;  // 기준 문자열 수 초기화
                }  
            }

			// 남은 기준 문자열을 압축 문자열 뒤에 추가
            if (count <= 1) {
                sb.append(now);
            } else {
                sb.append(count).append(now);
            }
            
            if (answer == 1) {  // 처음으로 압축인 된 경우
                answer = sb.length();  // 압축 문자열의 길이 저장
            } else {
                answer = Math.min(answer, sb.length());  // 기존 압축 문자열의 길이와 현재 압축 문자열의 길이 중 더 작은 값 저장
            }
        }
        
        return answer;
    }
}