프로그래머스-level1-문자열 압축

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

코딩테스트 연습 - 문자열 압축 | 프로그래머스

2020 카카오 알고리즘테스트 문제이다.(문자열 압축)

Level 1이 맞는지 심히 의심스럽다...

 

우선 전체적인 흐름은 전체길이의 중간값으로 문자열을 나누고 나눈 값끼리 비교하는 것이다.

밑에 코드를 이클립스에 넣어보면 과정들이 친절하게 나오게 해놨다.

 

밑에 코드는 같은 문자가 10개 이상 나온다는 것을 고려를 안하고 가라로 했다...(68점)

똑같은 문자 a가 1000개가 와도 1000a가 아닌 2a가 나온다...! 

import java.util.Arrays;

class Solution {
   public static void main(String args[]) {
      Solution s = new Solution();
      String st= "aabbaccc";
      System.out.println(s.solution(st));
      
      String st2 = "abcabcdede";
      System.out.println(s.solution(st2));
      
      String st3 = "ababcdcdababcdcd";
      System.out.println(s.solution(st3));
      
      String st4 = "abcabcabcabcdededededede";
      System.out.println(s.solution(st4));
      
      String st5 = "xababcdcdababcdcd";
      System.out.println(s.solution(st5));
   }
   
   public int solution(String s) {
      int sLength = s.length();
      // 최초 등분 값
      int startSp = sLength/2;
      
      int[] returnVal = new int[startSp];
   
      for(int j=startSp; j >0; j--) { 
         
         // 목값
         int quo = sLength/j;
         System.out.println(j+"등분을 시작합니다. 몫 : " + quo);
         // 몫 길이만큼 임시배열을 생성
         String[] tempString = new String[quo];
         // 나머지값
         String remainder ="";
         for(int i=0; i < quo; i++) {
            // 등분해서 임시배열에 넣음
            tempString[i] = s.substring(j*i, j*(i+1));
            if(i == quo-1 && s.substring(j*(i+1)) != "") {
               remainder = s.substring(j*(i+1));
            }
         }
         System.out.println("등분 값 : " + Arrays.toString(tempString)+ " 나머지 값" + remainder);
         int cnt =1;
         for(int i=0; i < quo-1; i++) {
            // 등분한 것의 i와 i+1 같을 경우
            if(tempString[i].equals(tempString[i+1])) {
               cnt++;
               if(cnt <= 2) {
                  tempString[i] = ""+cnt;
               } else {
                  tempString[i] ="";
               }
            } else {
               cnt = 1;
            }
         }
         String sum ="";
      
         for(int i =0; i < quo; i++) {
            sum += tempString[i];
         }
         System.out.println("리턴 값 : " + (sum.length() +remainder.length()));
      
         returnVal[startSp-j] = sum.length()+remainder.length();
         
      }
      Arrays.sort(returnVal);
      return returnVal[0];
      
   }
}

 

그리하여 알고리즘을 좀 손봤다.  카운트가 2 이하면 해당 배열의 i값을 공백으로 만들었고

3이상이면 i-1값을 공백, i값을  카운트, i+1은 변동 없게 해놨다.

 

추가적으로 테스트 케이스 5번이 틀렸는데 뭐지? 하고 찾다가

문자열 길이가 1인 케이스였다. equals 비교 자체가 안되므로 그냥 길이 확인해서 1리턴 하는 걸로... 해결^^

 

import java.util.Arrays;

class Solution {
	public static void main(String args[]) {
		Solution s = new Solution();
		String st= "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
		System.out.println(s.solution(st));
		
		String st2 = "aabbaccc";
		System.out.println(s.solution(st2));
		
		String st3 = "a";
		System.out.println(s.solution(st3));
	}
	
	public int solution(String s) {
		int sLength = s.length();
		if(sLength == 1) {
			return 1;
		}
		// 최초 등분 값
		int startSp = sLength/2;
		
		int[] returnVal = new int[startSp];
	
		for(int j=startSp; j >0; j--) { 
			
			// 목값
			int quo = sLength/j;
			System.out.println(j+"등분을 시작합니다. 몫 : " + quo);
			// 몫 길이만큼 임시배열을 생성
			String[] tempString = new String[quo];
			// 나머지값
			String remainder ="";
			for(int i=0; i < quo; i++) {
				// 등분해서 임시배열에 넣음
				tempString[i] = s.substring(j*i, j*(i+1));
				if(i == quo-1 && s.substring(j*(i+1)) != "") {
					remainder = s.substring(j*(i+1));
				}
			}
			System.out.println("등분 값 : " + Arrays.toString(tempString)+ " 나머지 값" + remainder);
			int cnt =1;
			for(int i=0; i < quo-1; i++) {
				// 등분한 것의 i와 i+1 같을 경우
				if(tempString[i].equals(tempString[i+1])) {
					cnt++;
					if(cnt <= 2) {
						tempString[i] = ""+cnt;
					} else {
						tempString[i-1] ="";
						tempString[i] = ""+cnt;
					}
				} else {
					cnt = 1;
				}
			}
			String sum ="";
		
			for(int i =0; i < quo; i++) {
				sum += tempString[i];
			}
			System.out.println("리턴 값 : " + (sum.length() +remainder.length()));
		
			returnVal[startSp-j] = sum.length()+remainder.length();
			
		}
		Arrays.sort(returnVal);
		return returnVal[0];
		
	}
}

 

나는 평균 속도가 40ms가 나왔는데 다른 사람꺼는 2~3ms가 나온게 있다.

이 코드는 스터디 때 분석해보는걸로....