[프로그래머스] 문자열 압축 - JAVA

문제 사이트
원본 String을 받아서 0번째 자리부터 일정 수 만큼 겹치는 문자를 압축 할 수 있을지 찾아보는 문제이다.

1. String을 받아서 얼마나 줄여지는지 확인하는 함수
2. 1번 함수를 사용해서 1부터 원본 String 길이의 1/2 만큼 압축결과를 확인

스켈레톤 코드

class Solution {
    public int solution(String s) {

        int answer = s.length();
        

        if (s.length() == 1) {
            return 1;
        }


        for (int unit = 1; unit <= s.length() / 2; unit++) {

            answer = Math.min(answer, getCompressedLength(s, unit));
        }
        
        return answer;
    }

	// 원본 문자열 s를 unit길이 만큼 압축한 결과
    private int getCompressedLength(String s, int unit) {
        //todo
    }
}

압축

문자열을 압축하는 과정은 다음과 같다.
1. 원본 문자열 s의 0번 자리부터 unit크기 만큼 currentUnit으로 설정한다.
2. currentUnit의 다음 자리부터 unit크기 만큼 nextUnit으로 설정한다.
3. currentUnit과 nextUnit을 비교하여 달라지는 경우가 나올때 가지 nextUnit을 s에서 지운다.

    private int getCompressedLength(String s, int unit) {
        StringBuilder compressed = new StringBuilder();
        int i = 0;


        while (i < s.length()) {

            if (i + unit > s.length()) {
                break;
            }
            
            // 1번
            String currentUnit = s.substring(i, i + unit);
            int count = 1;
            int nextPos = i + unit;

			// 2번
            while (nextPos + unit <= s.length()) {
                String nextUnit = s.substring(nextPos, nextPos + unit);
                if (currentUnit.equals(nextUnit)) {
                    count++;
                    nextPos += unit;
                } else {
                    break;
                }
            }


            if (count > 1) {
                compressed.append(count);
            }
            compressed.append(currentUnit);


            i = nextPos;
        }

		// 3번
        if (i < s.length()) {
            compressed.append(s.substring(i));
        }

        return compressed.length();
    }

문자열 삭제

• 처음에는 for문을 사용해서 반복문 안에 s를 변경하면서 문제를 풀었는데, 그러면서 for문에서 사용하는 index가 꼬이는 문제가 있었다.
• 그 문제는 반복문 바깥에 index를 두어 안전하게 푸는 방법으로 바꿨더니 해결되었다.
• 나의 실수를 최대한 줄일 수 있게 단순한 방법을 찾아가면서 문제를 풀자

이전 코드

반복문 안에서 문자열을 수정하는 경우 종료 조건인 i < s.length()의 인덱스를 예측하기 어려워진다.

 		for (int i = 0; i < s.length() - unit;) {

            String original = s.substring(i, i + unit);
            int equalCnt = 1;
            
            while (i + 2*unit <= s.length()) {
                String compare = s.substring(i + unit, i + 2*unit);

                if (original.equals(compare)) {
                    s = s.substring(0, i) + s.substring(i + unit, s.length());
                    equalCnt++;
                    continue;

                }

                break;

            }

수정 코드

반복문 바깥에 index를 두어 예측을 단순하게 한다.

        int i = 0;	// 반복문 바깥에 index


        while (i < s.length()) {

            if (i + unit > s.length()) {
                break;
            }
            
            // 1번
            String currentUnit = s.substring(i, i + unit);
            int count = 1;
            int nextPos = i + unit;

			// 2번
            while (nextPos + unit <= s.length()) {
                String nextUnit = s.substring(nextPos, nextPos + unit);
                ...
    

전체 코드

import java.util.*;

class Solution {
    public int solution(String s) {

        int answer = s.length();
        

        if (s.length() == 1) {
            return 1;
        }


        for (int unit = 1; unit <= s.length() / 2; unit++) {

            answer = Math.min(answer, getCompressedLength(s, unit));
        }
        
        return answer;
    }

    private int getCompressedLength(String s, int unit) {
        StringBuilder compressed = new StringBuilder();
        int i = 0;


        while (i < s.length()) {

            if (i + unit > s.length()) {
                break;
            }
            
            String currentUnit = s.substring(i, i + unit);
            int count = 1;
            int nextPos = i + unit;


            while (nextPos + unit <= s.length()) {
                String nextUnit = s.substring(nextPos, nextPos + unit);
                if (currentUnit.equals(nextUnit)) {
                    count++;
                    nextPos += unit;
                } else {
                    break;
                }
            }


            if (count > 1) {
                compressed.append(count);
            }
            compressed.append(currentUnit);


            i = nextPos;
        }


        if (i < s.length()) {
            compressed.append(s.substring(i));
        }

        return compressed.length();
    }
}