Look-and-say sequence(개미수열)

개미 수열(정규표현식)

Dev 코스 조그마한 과제였는데 처음에 정규표현식을 자유롭게 사용하지 못해 쉽게 풀지 못했습니다.
그러나 풀었습니다. :)

우선 개미 수열에 대해 알아야합니다. 영차 영차

1 -> 11 -> 21 -> 121 -> 111211 -> 311221 ...

 

다음과 같은 규칙을 가지는 데 처음에 이해를 잘 못했습니다. 힌트는 Run-length encoding입니다.

 

이해를 돕기위해 설명을 조금 더하자면

 

전 단계의 값에서 같은 수의 값 개수 + 값 을 구하는 것

ex)
"1"에서 "11"이 나오기 위해 1개의 1을 붙여 쓴 것이 "11"입니다.

"121"에서 "111211"이 나오기 위해 1개의 1 + 1개의 2 + 1개의 1을 숫자만 붙여써보면 "1111211"이 나옵니다.

즉, 현재 값 = 전 단계를 하나씩보며 "공통된 해당 값의 갯수" + "해당 값"

 

풀이

changeAnt()에서 정규 표현식으로 Run-length encoding을 진행합니다.
antSeq()에서 재귀를 사용하여 값을 구하게 됩니다.
현재 값은 5번째 값을 구하기 위한 것입니다.

 

const changeAnt = (val) => {
    const regExp = /(.)/1*/g;
    let result = val
        .match(regExp)
        .reduce((a,b) => a + `${b.length}${b.slice(0,1)}`,"");
    return (result);
}

const antSeq = (val, cnt) => {
    if (cnt - 1 == 0) {
        console.log(val);
        return ;
    }
    else antSeq(changeAnt(val), cnt-1);
}

antSeq("1", 5);

• /1* : 첫번째 문자열 있는지 확인

 

마치며

알고리즘을 풀때 완벽히 이해하고 손으로 로직을 짠 후에 코드를 짜는 것이 훨씬 속도가 빠르다는 것을 느꼈습니다.

그리고 정규 분포식이 완전 익숙하지 않아서 더 많이 연습해야 될 것 같습니다. :)

 

Ref

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions
https://ko.wikipedia.org/wiki/%EC%9D%BD%EA%B3%A0_%EB%A7%90%ED%95%98%EA%B8%B0_%EC%88%98%EC%97%B4
https://ko.wikipedia.org/wiki/%EB%9F%B0_%EB%A0%9D%EC%8A%A4_%EB%B6%80%ED%98%B8%ED%99%94