[프로그래머스] 2020 KAKAO BLIND RECRUITMENT - "문자열 압축" (Java)

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

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

 

문자열 압축

 

---

난이도 : Level 2

 

 

 제가 생각한 로직은 아래와 같습니다. 

1. 절반까지만 탐색한다. (절반이 넘어가면 반복되는 문자열이 없기 때문.)

2. 문자열에서 범위를 정하여 각 범위만큼 비교 문자열을 생성한다 (String slice)

3. s 문자열에서 비교 문자열 뒤로 target 문자열을 비교하며 임시 문자열을 만들어낸다. 

4. 임시 문자열과 정답 문자열의 길이를 비교하며 최소 길이를 추출한다. 

 

 

- int solution(s)

  입력을 받고, 범위만큼 compare 함수를 호출하는 일종의 main 함수입니다. HALF 변수로 절반의 길이까지만 범위를 설정하였습니다. 그 이유는 절반 이후부터는 연속되는 문자열이 나타나지 않기 때문입니다. 

 

 slice 변수에 0부터 지정한 범위만큼 문자열을 저장합니다. 

 

 compare 함수에서 return으로 얻은 문자열을  compare_str 변수에 저장합니다. 이 둘의 길이를 비교하여, 최종적으로 최소 길이를 추출하게됩니다.

 

 

- String compare(int len, String s, String slice)

 지정한 범위(len)로 s 문자열을 탐색합니다. 위에서 저장한 slice 변수가 초기 기준이 되고 뒤에 문자열을 계속해서 탐색하면서 slice 변수와 같으면 count를 증가시키고, 다르면 count의 값이 1인지 판단 후 반환 문자열인 result에 추가합니다.

 

 반복문을 다 돌았으면 마지막 위치에 있는 범위의 문자열은 result에 저장이 되지 않습니다. 이를 저장해주기 위하여 한번 더 if 문을 이용하여 추가합니다.

 

 

  코드

class Solution {
    public int solution(String s) {
        int answer = s.length();
        
        int HALF = s.length()/2;
        
        for(int i=1; i<=HALF; i++) {
        	String slice = s.substring(0, i);
        	
        	String compare_str = compare(i, s, slice);
        	
        	answer = Math.min(answer, compare_str.length());
        }
        
        return answer;
    }
    
    public String compare(int len, String s, String slice) {
    	
    	String result = "";
    	int count = 1;
 
       	for(int i=len; i<s.length(); i+=len) {
       		int limit = i+len;
       		if(i+len >= s.length()) {
       			limit = s.length();
       		}
    		String target = s.substring(i, limit);
    		if(slice.equals(target)) {
    			count++;
    		}
    		else {
    			if(count == 1) {
    				result += slice;
    			}
    			else {
    				result += (count + slice);
    			}
    			count = 1;
    			slice = target;
    		}
    	}
    	
    	if(count == 1) {
    		result += slice;
    	}
    	else {
    		result += (count + slice);
    	}

    	return result;
    }
}

 

Javascript 풀이 링크입니다. 

https://bbangson.tistory.com/93

[프로그래머스] 2020 KAKAO BLIND RECRUITMENT - "문자열 압축" (Javascript)

 

 

 

 

 

 

 

 

피드백 환영합니다.