[KAKAO_BLIND_RECRUITMENT_2020] 문자열 압축

문제

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

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

 

 

출제 의도

tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

• 문자열을 다룰 수 있고, 아래 예시와 같이 문자열과 관련된 다양한 작업을 할 수 있는지 파악
  • 문자열 자르기
  • 부분 문자열 얻기
  • 문자열 비교하기
  • 문자열 길이 얻기

 

 

풀이

• 문자열의 길이가 L 이라고 한다면, 압축의 기준이 되는 문자열의 길이는 최대 L/2 라 판단.
  단위 반복문의 기준을 1~L/2로 설정
  ex) L = 10, 5이상의 문자열로는 압축이 불가능.
• 이후 문자열을 검사 하는 경우, 남는 문자열을 판단하는 기준이 필요할 것이라 생각했고
  그에 따라 현재 index + unit(단위)의 크기로 판단을 설계.
• 문자열을 문제의 조건에 따라 풀이하면 되는 문제.

 

 

과정

1. 첫번째 for문 unit(자르는 단위)을 1씩 증가하며, 반복문 수행.
2. 두번째 for문 문자열 S에 대해 unit(단위만큼) 이동하며 반복문 수행.
3. 잘라야되는 문자열의 길이를 검사
   길이가 부족하지 않은 경우, unit단위 만큼 substring().
   길이가 부족한 경우, 해당 index부터 끝까지 substring().
   
   ex) 4개 단위로 자르는 경우
   →첫 단위를 자른 뒤 index = 0 에서 index = 4에 위치하고 있을 것이다.
   이후 4,5 로는 4글자의 문자열 생성이 불가능하다. (범위초과로 오류 발생가능)
4. 세번째 for문 앞선 for문의 문자 끝을 시작점으로 unit만큼 이동하며, 반복문 수행
5. 동일한 문자열이 아닌 경우 다시 반복문 수행
   but 동일한 경우 앞서 진행하던 2번째 for문의 idx의 위치도 함께 변경시킨다.
6. 세번째 for문을 탈출하면서 개수를 체크했던 cnt를 앞에 붙여준다.
7. 두번째 for문 종료 후, 최솟값 비교.
8. 첫번째 for문 종료 → 출력.

 

 

알고리즘 지식

• String

 

 

JAVA코드

package KAKAO_BLIND_RECRUITMENT_2020;

import java.io.IOException;

public class KAKAO_문자열압축 {

	public static void main(String[] args) throws IOException {
		// String s = "aabbaccc";
		// String s = "ababcdcdababcdcd";
		// String s = "abcabcdede";
		// String s = "abcabcabcabcdededededede";
		String s = "xababcdcdababcdcd";

		int len = s.length(); // 문자열이 길이
		int answer = len;

		// unit개 단위
		for (int unit = 1; unit <= len / 2; unit++) {
			StringBuffer tempSB = new StringBuffer();

			// 문자열 S에 대해
			for (int start = 0; start <= len; start += unit) {
				int end = start + unit;
				String word = "";

				// 남는 문자열을 위한 검사
				if (start + unit >= len) {
					word = s.substring(start);
				} else {
					word = s.substring(start, start + unit);
				}

				int cnt = 1;
				StringBuilder sb = new StringBuilder();

				// 남은 문자열에 대한 중복 검사
				for (int next = end; next < len; next += unit) {
					String word2 = "";

					// 남는 문자열을 위한 검사
					if (next + unit >= len) {
						word2 = s.substring(next);
					} else {
						word2 = s.substring(next, next + unit);
					}

					// 다음 문자열의 중복 여부 검사
					if (word.equals(word2)) {
						cnt++;
						start = next;
					} else {
						break;
					}
				}

				// 문자앞에 붙일 갯수
				if (cnt == 1) {
					sb.append(word);
				} else {
					sb.append(cnt).append(word);
				}

				tempSB.append(sb.toString());

			} // End of start

			// 최솟값 리턴
			answer = Math.min(answer, tempSB.toString().length());

		} // End of Unit

		System.out.println(answer);

	}

}