99클럽 코테 스터디 4일차 TIL + Java Algorithm

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL란? 'Today I Learned'약자로 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• 프로그래머스 - 문자열 압축 2020 KAKAO BLIND RECRUITMENT (문제 링크)
• 브루트 포스
• Queue

 

문제 설명

문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄이는 비손실 압축 방법을 공부하고 있습니다.

예를 들어, "aabbaccc"의 경우 "2a2ba3c"와 같이 표현할 수 있습니다. 하지만 반복되는 문자가 적을 경우 압축률이 낮아지는 단점이 있습니다. 예를 들어, "abcabcdede"는 전혀 압축되지 않습니다.

이를 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현하려고 합니다.

예를 들어, "ababcdcdababcdcd"는 2개 단위로 잘라서 압축하면 "2ab2cd2ab2cd"가 됩니다. 8개 단위로 잘라서 압축하면 "2ababcdcd"가 되며, 이때 가장 짧게 압축할 수 있습니다.

압축할 문자열 s가 주어질 때, 1개 이상 단위로 문자열을 잘라 압축한 문자열 중 가장 짧은 것의 길이를 반환하는 함수를 작성하세요.

제한사항

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

입출력 예

"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

입출력 예 설명

1. "aabbaccc": 1개 단위로 잘라 압축했을 때 가장 짧습니다.
2. "ababcdcdababcdcd": 8개 단위로 잘라 압축했을 때 가장 짧습니다.
3. "abcabcdede": 3개 단위로 잘라 압축했을 때 가장 짧습니다.
4. "abcabcabcabcdededededede": 6개 단위로 잘라 압축했을 때 가장 짧습니다.
5. "xababcdcdababcdcd": 압축되지 않으므로 가장 짧은 길이는 17입니다.

 

문제 접근

• 문자열의 최대 길이가 1000 이하인 점을 고려하여 완전 탐색을 통해 문제를 풀어보았습니다.
• "aabbaccc"가 주어졌을 때, Queue를 활용하여 각 Size 만큼 압축한 문자를 큐에 넣습니다.
• 큐는 FIFO(First In, First Out) 구조이므로, 왼쪽부터 하나씩 꺼내면서 연속된 문자의 개수를 세고, 다른 문자가 나오면 "count + 왼쪽문자열" 형태로 결과 문자열을 구성했습니다.
• 큐가 빌 때까지 반복합니다. 이렇게 얻은 결과 문자열의 길이를 초기 길이와 비교하여 더 작은 값을 저장합니다.
• 문자열의 절반 길이까지 반복하여 가장 짧은 압축 문자열의 길이를 구할 수 있습니다.

 

풀이 - Queue 활용

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {

    public int solution(String s) {
        int length = s.length(); // 1. 초기 문자열의 길이를 저장합니다.

        // 2. 부분 문자열의 길이를 1부터 s의 길이까지 증가시키며 반복합니다.
        for (int size = 1; size <= s.length(); size++) {
            Queue<String> q = new ArrayDeque<>(); // 부분 문자열을 저장할 큐를 생성합니다.

            // 주어진 크기(size)만큼 문자열을 잘라 큐에 저장합니다.
            for (int j = 0; j <= s.length() - size; j += size) {
                q.offer(s.substring(j, j + size)); // 부분 문자열을 큐에 추가합니다.
            }

            String result = s; // 압축 결과를 저장할 문자열을 초기화합니다.

            // 3. 큐가 빌 때까지 반복하여 문자열을 압축합니다.
            while (!q.isEmpty()) {
                int count = 1;
                String left = q.poll(); // 큐에서 부분 문자열을 하나 꺼냅니다.

                // 다음 부분 문자열이 현재 문자열과 같으면 카운트를 증가시킵니다.
                while (!q.isEmpty() && left.equals(q.peek())) {
                    q.poll();
                    count++;
                }

                // 동일한 문자열이 연속으로 나타난 경우 압축합니다.
                if (count > 1) {
                    String replace = "";
                    // 동일한 문자열을 반복하여 생성합니다.
                    for (int i = 0; i < count; i++) {
                        replace += left;
                    }
                    // 압축된 문자열로 대체합니다.
                    result = result.replaceFirst(replace, count + left);
                }
            }

            // 4. 압축된 문자열의 길이가 현재 최소 길이보다 짧으면 갱신합니다.
            length = Math.min(length, result.length());
        }

        return length; // 가장 짧은 압축 문자열의 길이를 반환합니다.
    }
}

풀이 설명

1. 문자열 길이 저장:
   • 초기 문자열의 길이를 length 변수에 저장합니다.
2. 부분 문자열 추출:
   • size 변수를 1부터 문자열의 길이까지 증가시키며 반복합니다.
   • 각 size만큼 문자열을 잘라 큐(Queue)에 저장합니다.
3. 문자열 압축:
   • 큐에서 문자열을 하나씩 꺼내며 연속된 동일한 문자열을 찾아 압축합니다.
   • 압축된 문자열을 result 변수에 저장합니다.
   • 압축된 문자열의 길이가 현재 최소 길이(length)보다 짧으면 갱신합니다.
4. 결과 반환:
   • 최종적으로 가장 짧은 압축 문자열의 길이를 반환합니다.

 

---

 

마무리하며

• 이번 문제를 해결하면서 문자열 압축의 다양한 방법을 공부할 수 있었습니다. 완전 탐색을 통해 가능한 모든 단위로 문자열을 잘라 압축하고, 가장 짧은 결과를 찾는 과정에서 큐를 활용하여 부분 문자열을 관리하고, 연속된 문자열을 처리하는 방법을 적용해 보았습니다.
• 비록 큐를 사용한 방식이 직관적이고 이해하기 쉽지만, 문자열 조작에서의 성능 최적화와 개선의 여지를 항상 고민해봐야 한다는 점도 느꼈습니다.