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

문제내용

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

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

 

---

문제 접근 방법

문자열 관련 문제를 안풀어봐서 처음에 어떻게 풀어야할지 감이 안잡혔다.

그리고 최근까지 풀었던 BFS, DFS 밖에 생각이 안나서 큐를 만들어서 큐에 비교 문자열을 넣어서 비교하려고하고,,, 재귀로도 해보려하고... 삽질을 했다.

 

답을 참고하여 풀어보니 큐나 재귀를 이용해서 풀수도 있겠단 생각이 들었지만 중요한건.

 

문자열을 나누는 기준과 나눈 문자열을 다음 문자열과 비교할수 있는 방법에대한 로직을 생각하지 못해서 못푼거라고 생각한다.

 

아래 풀이에서는

1. 문자열을 압축할땐 문자열 절반크기보다 큰 단위로 압축할수 없다.
2. 문자열을 압축하려면 압축크기로 나눈 비교문자열을 담을 변수와 만들어진 문자열을 담을 변수가 필요하다.
3. 비교문자열과 다음 문자열을 비교한다. 예) 압축크기가 3일때 (0,3) 과 (3,6)을 비교.
4. 비교 후 문자열이 두개가 같으면 int cnt 변수에 +1을 해준다.

4가지가 가장 중요하다 생각한다.

위의 것을 구현하려면 압축크기가 1, 2, 3 ... s.length()/2 까지 경우 하나하나를 생각해야하고

각 압축크기마다 문자열을 비교할수 있어야한다.

 

결국 압축크기를 나타내는 for문과 압축크기가 정해졌을때 문자열을 비교하는 for문 즉, 이중for문이 필요하다.

 

아래 풀이를 보면서 생각해보자.

 

---

 

풀이

/**
 * 문자열 압축
 * kakao
 * @author USER
 *
 */
public class stringPress {
	static int MIN = Integer.MAX_VALUE; //압축했을때 최소길이를 구하기위한 변수
    
	public static int solution(String s) {
		int answer = 0;
		
		if(s.length()==1) { //입력 문자가 1글자면 길이 1을 그대로 리턴.
			return 1;
		}
		
		//이중for문에서 i는 몇글자 단위로 압축시도 할건지 나타냄.
		//j는 글자 압축단위를 i로 했을때 문자열 앞에서부터 i단위로 나눠주며 잘라낸 문자열을 다음 문자열과 비교하기 위한 변수임.
		for(int i=1; i<=s.length()/2; i++) {// 문자열 s의 길이 절반보다 크면서 압축하는건 불가능.
			String str = ""; // 각경우마다 최종 문자열.
			String com = ""; // 비교할 문자열(i 단위로 나눈 앞의 문자열)
			int cnt = 1;
			
			//j=0부터 i 단위로 문자열 압축을 할것이기 때문에 문자열 크기를 i로 나누고 for문 돌림
			//s.length()/i를 포함 못하는이유는 substring의 인덱스값이 넘어감.
			//따라서 for문 끝나고 마지막 문자열을 붙여줘야한다.
			for(int j=0; j<s.length()/i; j++) {
				/* 첫번째 if문에서 com과 같은 크기의 그다음 문자열이 같으면 cnt++;
				 * 예를들어 i가 4일때
				 * com -> (0,4) 라면
				 * s.substring(i*j, (i*j)+i)) -> (4,8) 이고
				 * 두개가 (0,4) 와 (4,8)이 같다면 i단위로 압축되는 문자열이므로
				 * cnt++이 된다.
				 * 그리고 압축이된다면 com는 (8,12)와 비교해야하기 때문에
				 * continue를 이용해 다음 문자열을 바로 검사한다.
				 */
				if(com.equals(s.substring(i*j, (i*j)+i))){
					cnt++;
					continue;
				}
				
				if(cnt>1) { //cnt가 2이상이면 cnt+com를 str에 붙임.
					str += cnt+com;
					cnt=1; //붙였으니까 cnt=1로 초기화
				}else { //cnt가 1이면 압축안된거라 그냥 바로 com를 str에 붙임.
					str += com;
				}
				
				com = s.substring(i*j, (i*j)+i);//다음 비교문자열을 com에 할당.
			}//for(j)
			
			//위의 for(j)에서 마지막의 문자열은 붙여주지못해서 여기서 붙여줘야함.
			if(cnt>1) {
				str += cnt+com;
			}else {
				str += com;
			}
			
			//i로 문자열이 안떨어질땐 길이를 i로 나눈 나머지가 맨뒤에 남은 글자수가됨.
			//그 글자수를 str에 마지막으로 붙여주면된다.
			if(s.length()%i!=0) {
				str += s.substring(s.length()-s.length()%i, s.length());
			}
			
			MIN = Math.min(MIN, str.length());//for(i)끝날때까지 비교 후 최소값을 구함
		}//for(i)
		
		answer = MIN;
		return answer;
	}
}

 

---

마치며

문자열 문제를 이제 풀어보기 시작했는데... 막상 풀고나서 코드를 살펴보면 어렵지 않다.

하지만 코드를 짜기전에 문제의 조건들을 어떻게 만족시키며 코드를 짜야할지 아직은 미숙한 감이 있다.

공부열심히 하자..!!