[알고리즘] 개미수열 (읽고 말하기 수열)

설명

개미수열이란, 읽고 말하기 수열 <-> 개미수열

우리나라에서는 소설 '개미'에서 소개되면서 유명해졌기 때문에 "개미 수열" 이란 이름으로 알려져 있다.

1, 11, 12, 1121, 122111, 112213, ....

 

이 수열은 앞의 수를 연속된 같은 수의 개수로 묶어서 읽는 방식이다.

예를 들면,

- 1을 1이 1개 : 11

- 11을 1이 2개 : 12

- 12를 1이 1개 2가 1개 : 1121

- 1121을 1이 2개 2가 1개 1이 1개 : 122111

- ...

 

성질

- 22로 시작한 수열은 22, 22, 22, ... 로 길이가 더이상 늘어나지 않는다.

- 수열에서 1, 2, 3이 아닌 수는 등장하지 않는다

개미수열과 비슷한 원리를 가진 알고리즘으로는 반복 길이 부호화(Run-length encoding)가 있다.  반복 길이 부호화는 매우 간단한 '비손실 압축 방법'으로 데이터에서 같은 값이 연속해서 나타나는 것을 그 개수와 반복되는 값만으로 표현하는 방법이다. 이 방법은 아이콘, 간단한 이미지와 같이 연속된 값이 많이 있는 데이터에 효과적이다.

 

코드

코드로 개미수열을 이해해보자.

아래 코드는, 전달받은 양의 정수값(n)만큼 개미수열을 진행했을 때 돌아오는 값이 무엇인지 찾아내는 문제이다.

function makeAnt(s) { 
    let str = '';
    let char = s.charAt(0); // '1'
    let cnt = 1;

    for(let i=1; i<s.length; i++) {
        if(char === s.charAt(i)) {
            // 개수를 세기 위해 카운트 값만 증가 시킨다
            cnt++;
        } else {
            // 값이 달라지면 기존에 잡았던 초기값과 카운트를 더해서 문자열을 만들어준다.
            str = str + char + cnt;

            // 달라진 문자열을 기준으로 잡기위해 변경
            // char !== s.charAt(i)
            char = s.charAt(i);

            // 달라진 문자열 기준으로 새로운 개수를 세기 위해 카운트를 초기화
            cnt = 1;
        }
    }

    str = str + char + cnt;
    return str;
}

function solution(n) {
    var answer = "1";

    for(let i=0; i<n; i++) {
        console.log(`>> Loop Count : ${i}`);
        answer = makeAnt(answer);
    }

    return answer;
}

// 최종 값 확인!
console.log('>> [ RESULT ] : ', solution(5));