[자바스크립트] 개미 수열 풀이

개미수열은 다음과 같은 수열입니다. (이 수열은 소설 개미에서 소개되었기 때문에 개미 수열이라고 불립니다.)

 1, 11, 12, 1121, 122111 ..... 이 수열은 앞의 수의 연속된 같은 숫자를 묶어서 숫자와 그 개수를 읽는 방식으로 만들어집니다. 1을 1이 한 개 혹은 11로 읽습니다. 11을 1이 두 개 혹은 12로 읽습니다. 12를 1이 한 개, 2가 한 개 혹은 1121로 읽습니다. 1121을 1이 두 개, 2가 한 개, 1이 한 개 혹은 122111로 읽습니다. 

이와 같은 방법으로 계속해서 다음 수를 만들어 갑니다. 입력으로 n 이 주어질 때 n번째 개미 수열을 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

// 개미수열은 다음과 같은 수열입니다. (이 수열은 소설 개미에서 소개되었기 때문에 개미 수열이라고 불립니다.)

// 1, 11, 12, 1121, 122111 ..... 이 수열은 앞의 수의 연속된 같은 숫자를 묶어서 숫자와 그 개수를 읽는 방식으로 만들어집니다.

// 1을 1이 한 개 혹은 11로 읽습니다. 11을 1이 두 개 혹은 12로 읽습니다. 12를 1이 한 개, 2가 한 개 혹은 1121로 읽습니다.

// 1121을 1이 두 개, 2가 한 개, 1이 한 개 혹은 122111로 읽습니다. 이와 같은 방법으로 계속해서 다음 수를 만들어 갑니다.

// 입력으로 n 이 주어질 때 n번째 개미 수열을 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

function solution(s) {

// 배열 두개를 만들어서, 같은 그룹 끼리 묶인 배열 arr2와, 그것을 모두 감싸는 배열 arr1를 만들었다.

let arr1 = [];

let arr2 = [];

// 문자열 s의 처음부터 순회를 도는데, 현재와 다음 문자열이 같다면 arr2에 맨 처음 숫자를 떼서 저장하고,

// s에 첫 숫자가 떨어진 나머지 문자열을 다시 저장한다.

// 만약 같지 않더라도 똑같은 작업을 해준뒤, 추가로 이때까지 저장한 arr2를 arr1에 push하고, arr2는 초기화 한다.

// 이것을 s의 길이가 0이 될 때까지 한다.

while (s.length !== 0) {

if (s[0] === s[1]) {

arr2.push(s[0]);

s = s.replace(s[0], "");

} else {

arr2.push(s[0]);

s = s.replace(s[0], "");

arr1.push(arr2);

arr2 = [];

}

}

// 문자열 분해 과정이 다 끝났다면, arr1에는 같은 숫자끼리 묶인 arr2 배열이 요소로 들어가 있을 것이다.

// 이것을 forEach문으로 순회하여, 빈 문자열 answer에 '배열의 값+그 배열의 길이' 로 저장한다.

// 저장한 문자열 answer를 리턴한다.

let answer = "";

arr1.forEach(val => {

answer += `${val[0]}${val.length}`;

});

return answer;

}

function ant(n) {

if (n === 1) return "1"; // n이 1이면 문자열 '1'을 리턴한다. 재귀함수의 종료 조건이다.

// solution 함수에 ant 함수 인자로 받은 n에서 -1을 해준 값을 ant()에 넣어주고

// ant 함수가 리턴한 문자열이 solution에 들어가도록 만든다.

return solution(ant(n - 1));

}

console.log(ant(20));

// 이 문제의 핵심은 연속된 같은 숫자를 묶는 방법에 있다.

// 먼저 문자열로 인자를 받는 함수 solution을 만들었다.

// 이 함수는 앞의 수를 읽는 방법을 알고리즘으로 만든 것이다.

// 나도 내가 이것을 풀었다는 사실이 믿기지가 않는다.

9월 7일에 내가 입사 코딩 테스트로 받은 문제중 하나. 그때는 거의 멘붕이어서 손도 못댔는데 요즘 알고리즘 공부하다보니까 샤워하다가 문득 이걸 재귀로 풀수 있겠다는 생각이 들어서 풀었다.

풀이법은 주석으로 남겨놓았다.

아주 자랑스럽다.