프로그래머스 level2 문자열 압축

최근 매일마다 알고리즘 문제를 최소 하나씩은 풀고 있다. 그런데 쉬운 문제로 보이는데도 힘들게 고생한 문제가 있어, 이대로 풀고 보내기 아쉬운 마음에 포스팅을 하려 한다.

보통은 알고리즘 문제가 40분 이상 걸리면 포기하고 풀이를 보라고 한다. 하지만 분명 풀 수 있을 것 같은 문제가 테스트케이스 하나 때문에 틀린다면 자존심 때문에라도 풀이를 볼 수 없다. 그렇게 3시간이 걸렸다...

첫 풀이

function solution(s) {
  let answer = [];
  let cnt = 1;
  for (let i = 1; i <= s.length / 2; i++) {
    let words = "";
    let _s = s.slice();
    while (_s.length >= i) {
      let word = _s.substring(0, i);
      _s = _s.substring(i);
      if (word === _s.substring(0, i)) {
        cnt++;
      } else if (word !== _s.substring(0, i)){
        if (cnt === 1) {
          words += word;  
        } else {
          words += (cnt + word);
        }
        cnt = 1;
      }
    }
    if (cnt === 1) {
      words += _s;  
    } else {
      words += (cnt + _s);
    }
    answer.push(words.length)
  }
  return Math.min(...answer);
}

‘일단 치고 보자’ 라는 생각으로 작성했던 풀이였다. 자꾸 테스트케이스 5번이 실패가 뜨는데, 아무리 코드를 살펴봐도 무엇이 잘못되었는지를 몰랐다. 내가 짠 코드였지만 내가 봐도 어떻게 돌아가는지를 이해하기 어려웠고, 이 때문에 코드를 대충 짜는 과정에서 코드가 꼬였거나 불필요한 코드가 생겨났다고 생각해서 다시 코드를 짰다.

두번째 풀이

function solution(s) {
  let answer = [];
  for (let i = 1; i <= s.length / 2; i++) {
    let words = "";
    let _s = s.slice();
    while (_s.length) {
      let cnt = 1;
      let word = ""; 
      while (_s.length >= i * cnt && _s.substring(0, i) === _s.substring(i*cnt, i * (cnt+1))) {
        word = _s.substring(0, i);
        cnt++;
      }
      if (cnt > 1) {
        words += cnt + word;
        _s = _s.substring(i*cnt);
      } else {
        words += _s[0];
        _s = _s.substring(1);
      }
    }
    answer.push(words.length)
  }
  return Math.min(...answer);
}

두 번째 풀이를 하기 전, 틀리는 테스트 케이스를 생각해냈다. 바로 "aacdacd" // a2acd 5 이라는 테스트 케이스인데, 돌릴 때 마다 2acdacd 가 뜨면서 5가 나오질 않았다. 그래서 i 칸씩이 아닌, 1칸씩 체크하며 확인하도록 하는 풀이를 만들어냈다.

잘못된 테스트 케이스로 인한 대참사

위의 풀이는 "aacdacd" // a2acd 5 를 뱉어내면서 완벽히 돌아갔다. 맨붕의 순간은 프로그래머스 사이트에서 이 코드를 돌렸을 때다. 기본 테스트 케이스인 "xababcdcdababcdcd" // 17 이 실패하면서, 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 라는 조건을 발견한 것이다.. 사실 첫 번째 풀이에서 "aacdacd" // a2acd 5 이 나오지 않았던 것은, 정해진 길이만큼 자르는 조건을 충족했기 때문이고, 첫 번째 풀이가 맞는 풀이었던 것이다.

세번째 풀이

function solution(s) {
  let answer = [s.length];
  for (let i = 1; i <= s.length / 2; i++) {
    let words = "";
    let _s = s.slice();
    while (_s.length) {
      let cnt = 1;
      let word = ""; 
      while (_s.length >= i * cnt &&
        _s.substring(0, i) === _s.substring(i * cnt, i * (cnt + 1))) {
        word = _s.substring(0, i);
        cnt++;
      }
      if (cnt > 1) {
        words += cnt + word;
        _s = _s.substring(i*cnt);
      } else {
        words += _s.substring(0,i);
        _s = _s.substring(i);
      }
    }
    answer.push(words.length)
  }
  return Math.min(...answer);
}

위의 풀이를 i칸씩 확인하도록 수정한 뒤, 코드를 다시 살펴보니 진짜 문제를 발견했다. 문제는 i <= s.length/2 에 있었다. 주어진 문자열의 길이가 1일 경우, 1<1/2 로써 코드가 진행되지 않던 것이다. 이를 해결하기 위해 answer에 기본적으로 문자열의 길이를 넣어주면서 해결했다.

읽기 쉬운 코드의 필요성

당연한 이야기 임에도 항상 놓치는 것이 있다. “읽기 쉬운 코드를 짜라” 머릿속에서 정리조차 하지 않은 채 손이가는 대로 풀다보니 내 코드도 이해 못하고, 문제를 의심하여 잘못된 테스트 케이스도 만들어 내는 대참사가 벌어지게 되었다. 당장의 문제를 해결하는 if else 범벅의 스파게티 코드를 멀리하고, 문제의 원인을 파악하고 최소한의 사이드이펙트 코드를 짜야 한다는 당연한 교훈을 새기며, 눈물의 3시간 풀이를 마친다.