[알고리즘 TIL] 문자열 합치기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/60057?language=java

프로그래머스

트러블 슈팅

이 문제는 단순 구현이지만, 구현 전에 경우의 수에 따른 시나리오를 잘 짜서 빈틈없이 구현하는 게 중요했다.

1. 압축 단위를 1 ~ s.length()/2까지 순회하면서,
2. 문자열을 그 단위로 잘라가며:
	이전 조각(pre)과 다음 조각(next)을 비교
	같으면 count++
	다르면 (count > 1이면 count + pre, 아니면 pre만 저장)
3. 문자열이 끝났을 때 남은 조각과 count까지 처리
4. 가장 짧은 압축 길이를 업데이트

 

또한, 마지막에 1를 제거하려고 했지만, 1 뿐만 아니라 10, 11 같이 1 포함 다른 수들에서도 1이 없어지는 오류가 발생해서, replace 대신 count > 2 일 때만 count를 문자열로 바꿔 더해주었다.

코드 구현

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

            //합칠 갯수는 1부터 전체 문자열 길이의 반까지 반복
            for (int i = 1; i <= s.length() / 2; i++) {
                int count = 1;
                String preStr = "";
                String nextStr = "";
                String result = "";
                for (int j = 0; j < s.length(); j++) {
                    nextStr += s.charAt(j);

                    //문자열이 맨 앞인 경우
                    if(preStr.equals("")){
                        if((j+1)%i==0){
                            preStr = nextStr;
                            nextStr = "";
                        }
                        continue;
                    }

                    //문자열이 맨 앞이 아닌 경우부터 이전 문자열과 비교
                    //i만큼 문자열을 다 묶었을 때
                    if((j+1)%i==0){
                        if(preStr.equals(nextStr)) {
                            //이전 문자열과 같으면 갯수 +1
                            count++;
                        } else {
                            //같지 않으면 최종 문자열에 (갯수+문자열) 끝에 붙인 후 갯수 초기화
                            if (count > 1) result += count;
                            result += preStr;
                            count = 1;
                        }

                        //문자열이 끝난 경우
                        if(j==s.length()-1){
                            if (count > 1) result += count;
                            result += nextStr;
                        }

                        //preStr 갱신
                        preStr = nextStr;
                        nextStr = "";
                        continue;
                    }

                    //묶고 문자가 남았다면 모두 결과 문자열 끝에 붙임
                    if(j==s.length()-1){
                        if (count > 1) result += count;
                        result += preStr;
                        result += nextStr;
                    }
                }
                if(result.length()<answer) {
                    answer = result.length();
                }
            }
            return answer;
        }
}