[프로그래머스] 2020 KAKAO 블라인드 _ 문자열 압축

2021_07_11 문제 풀이

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

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

 

문제

 

의사코드

// s를 1부터 s.length 까지의 단위로 잘라 압축했을 때 가장 짧은 것을 리턴한다
// 결과를 담을 빈배열 변수 선언
// s의 길이만큼 while 문을 순회한다 ) 단위마다 s를 잘라보기 위함 변수 i 선언
  // s를 일단 split으로 모두 쪼갠다 string.split ex ) ["a", 'b', ...]
  // 단위 1개를 저장할 임시 배열을 선언 unitARR
  // string 값을 저장할 빈문자열 선언 mergedString
  // 쪼갠 배열을 순회한다
    // 만약,  mergedString의 길이가 i(단위)와 같지 않다면
       // mergedString += 쪼갠 배열의 요소를 더해준다
    // 만약, mergedString의 길이가 i(단위)와 같거나 ! 현재 인덱스가 마지막이라면 (남은 것)
      // 배열에 mergedString을 넣어준다
      // mergedString = "" , 변수 초기화
 
     // formattingString 빈문자열 선언
    // 빈객체 선언 {  unitArr[i] : {count, index} }...
    // unitArr을 순회한다
      // 만약 객체에 unitArr[i] 를 키로 가진 값이 이미 있다면
        // 만약, 그 인덱스가 i - 1이랑 같을 때 count를 1 증가 / 그 인덱스 값을 현재 i값으로 재할당
      
      // 키가 없으면 
        // unitArr[i - 1]의 키를 가진 값이 있다면, 
            // unitArr[i - 1]의 카운트가 2이상이라면
                //formattingString에 더해준다 formattingString += `${count}${unitArr[i-1]}`
                // 그리고 unitArr[i - 1]의 키와 값을 지워준다

            // 그렇지 않다면 ( 중복되지 않는 1개 일때)
                //   formattingString에 그냥 unitArr[i-1]을 더해주고
                // // 그리고 unitArr[i - 1]의 키와 값을 지워준다
            // unitArr[i]의 값을 할당한다

        // 그렇지 않다면 처음 인덱스인 경우만?
          // unitArr[i]의 값을 할당한다
      // formattingString.length 를 result 배열에 추가한다
    

  // 이것을 단위마다 반복해서 result에서 Math.min을 이용, 최솟값을 찾아 리턴한다

코드를 쓰기 전에 항상 많은 시간을 투자해서 수도 코드를 작성하는 스타일인데, 실제로 코드를 작성할 때는 클린 코드를 위해 변수 상수 명이나 구조를 조금씩 바꿔서 진행을 하기도 한다.

 

풀이

function solution(s) {
	// 길이가 1인 경우 바로 종료
    if (s.length === 1) return 1;
    
    const result = [];
    
    let unitNum = 1;
    // s를 각 단위마다 처리하기 위해 while 문으로 순회
    while ( unitNum < s.length) {
        const sArr = s.split("");
        const unitArr = [];
        let tempStr = "";
        
        // 요소 하나마다 단위를 확인하고, 단위에 맞게 unit으로 만들어 unitArr의 요소로 추가
        sArr.forEach((str, idx) => {
            if (tempStr.length !== unitNum) {
                tempStr += str;
                if (tempStr.length === unitNum) {
                    unitArr.push(tempStr);
                    tempStr = "";
                }
            } else {
                tempStr = str;
            }
            if (idx === sArr.length - 1 && tempStr !== "") {
                unitArr.push(tempStr)
            }
        })

		
        let formattingString = "";
        let obj = {}; // ex) { "aa" : {index: 1, count: 2},  ...}
        
        // unitArr 순회, obj에 키로 unit을 저장
        // obj[unitArr[i]].index 로 직전 요소와 동일한 지 확인하며 순회 및 카운팅
        
        for (let i = 0; i < unitArr.length; i++) {
            if (obj[unitArr[i]]) 
                if (obj[unitArr[i]].index === i - 1) {
                    obj[unitArr[i]].count++;
                    obj[unitArr[i]].index = i;
                    if (obj[unitArr[i]].count >= 2 && i === unitArr.length - 1) {
                        formattingString += `${obj[unitArr[i - 1]].count}${unitArr[i-1]}`;
                    }
                }
            } else {
                if (obj[unitArr[i - 1]]) {
                    if (obj[unitArr[i - 1]].count >= 2) {
                        formattingString += `${obj[unitArr[i - 1]].count}${unitArr[i-1]}`;
                    } else {
                        formattingString += unitArr[i - 1];
                    }
                    delete obj[unitArr[i - 1]];
                } 
                obj[unitArr[i]] = {count: 1, index : i};
                if (i === unitArr.length - 1) {
                    formattingString += unitArr[i]
                }
            }
        }
        result.push(formattingString.length);
        // 단위마다 반복
        unitNum++;
    }
    // 배열 내 최솟값을 리턴
    return Math.min(...result)
}

시간 복잡도 O(n^2)

2시간 반 걸렸다. 수도 코드를 저렇게 많이 써본 게 얼마만인지 .. 새벽에 피곤한 상태로 풀어서 더 힘들었던 것 같은데 오기가 생겨서 풀어내긴 했다. 가장 큰 문제는 코드를 이해하기가 굉장히 어렵다는 것..

다시 리팩토링을 해볼 예정이다.