[Algorithm] 프로그래머스 - 문자열 압축 (Java)

[문제]

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

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

[풀이]

보자마자 든 생각은 일단 i개의 갯수만큼 문자열을 잘라 현재 문자열과 전 문자열을 비교하여 압축하여 풀어야 하고 i는 1부터 주어진 문자열 s 길이 / 2 까지 가능하다는 것이었다.

만약 문자열 길이가 7이라면 3까지는 쪼개서 비교가 가능하지만 4개씩 쪼개서 비교할 수가 없다는 것이다.

문자열은 substring()으로 나눠서 전 문자열과 비교하는데 만약 문자열 길이가 7인데 3개씩 자른다면 substring(0,3), substring(3,6)이고 마지막 문자열은 substring(7,9)가 아닌 substring(7)인데 이걸 어떻게 풀어야 하나 고민했었다.

다른 분들의 코드를 보니 생각보다 쉽게 풀 수 있다는 것을 알았다. 

 

1. for문을 s 길이 /2만큼 돌린다 (변수 i)

• i는 몇글자씩 자를지 결정
• 길이 / 2를 넘으면 압축이 불가능
• for문 안에 압축된 문자열을 반환하는 compression 함수를 호출

2. compression

• 압축되었는지 여부를 확인할 count 변수는 1로 초기화
• s.length() + i 만큼 for문을 돌리고, 증감식은 j+=i로 설정 (왜냐하면 전의 문자열 & 현재 문자열과 비교하는 것이기에 마지막에 잘린 문자열이 전의 문자열이 되어야 함, 현재 문자열은 공백으로 설정하여 비교하면 된다. 따라서 j의 최댓값을 위와 같이 설정)
  
  • 전 문자열과 비교할 현재 문자열을 구한다.
    • 현재 문자열이 마지막 문자열이면 j부터 끝까지
    • 그외는 j+i
  • j가 0이 아니면 (현재 문자열이 맨 처음이라면 비교하지 않음)
    • 전 문자열과 현재 문자열을 비교해서 같으면 count++;
    • 전 문자열과 현재 문자열이 다르고 count가 2회 이상이면 => 전체 압축 문자열 += count + 전 문자열
    • 위 2가지 경우 모두 해당되지 않는다면 =>전체 압축 문자열 += 전 문자열
  • 현재 문자열을 전 문자열로 바꿔준다.
  • 반복이 모두 끝나면 전체 압축 문자열을 리턴

3. compression 결과 값의 길이, answer의 길이를 비교해서 더 작은 값을 answer에 대입

 

[코드]

class Solution {
    public int solution(String s) {
        int answer = s.length();

        for(int i=1;i<=s.length()/2;i++){
            answer = Math.min(answer, compression(s,i).length());
        }
        return answer;
    }

    /**
     * 문자열 압축
     *
     * @param str 입력받은 문자열
     * @param i i값
     * @return 압축된 문자열
     */
    private String compression(String str, int i){
        String pattern = "";    // 비교 대상이 될 전 문자열
        String compression = "";
        int count = 1;

        for(int j=0;j<=str.length()+i;j+=i){
            String nowStr = ""; // 전 문자열과 비교할 현재 문자열

            if(j >= str.length()){  // 현재 문자열이 없을때
                nowStr = "";
            }else if(j + i > str.length()){ // 마지막 문자열일때
                nowStr = str.substring(j);
            }else{
                nowStr = str.substring(j, j+i);
            }

            // 1. 전문자열과 같은지 비교 (맨 처음 문자열이라면 비교X)
            if(j != 0){
                if(nowStr.equals(pattern)){ // 같다면
                    count++;
                }else if(count >= 2){   // 다르고 count가 2회 이상이면
                    compression += count + pattern;
                    count = 1;
                }else{  // 압축 불가능하고 위의 경우 모두 해당사항 없다면 바로 문자열 붙이기기                    compression += pattern;
                }
            }
            // 현재 문자열을 전 문자열로 변경
            pattern = nowStr;
        }
        return compression;
    }
}

 

[참고 블로그]

https://velog.io/@ajufresh/%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-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java

[프로그래머스] 문자열 압축 문제풀이 (Java)