정규 표현식을 이용한 개미수열 구현 - JavaScript

프로그래머스 데브코스 3기

정규표현식을 활용한 개미 수열 구현  

Run-length Encoding

---

정규표현식에 대해 학습하며 개미 수열을 구현하는 과제를 진행했습니다. 정규표현식 학습에 도움이 많이 되었고 Run-length Encoding에 대해 알게 되어 학습했던 내용을 공유하고 기록하고자 글을 작성하게 되었습니다.

시작하기에 앞서 개미수열과 Run-length Encoding에 대해 간략하게 정리 후 이를 구현하는 방법에 대해 작성하려고 합니다.

---

개미 수열

읽고 말하기 수열이라고도 불리는 개미 수열은 베르나르 베르베르의 소설 개미에 등장한다고 하여 개미 수열이라고 불리게 되었습니다.

수열이라는 이름에서 알 수 있듯이 어떠한 규칙을 가지고 다음 수를 만드는 방식이다.

1부터 시작하여 이전 value들을 말하듯 표현하는 방식으로 아래의 표와 같이 1은 한 개의 1이므로 11, 11은 두개의 1이므로 21, 21은 한개의 2와 한개의 1이므로 1211과 같은 방식으로 수열을 완성한다. (천천히 생각하다 보면 쉽게 이해할 수 있다.)

Index	Value
1	1
2	11
3	21
4	1211
5	111221
...	...

개미 수열 - 읽고 말하기 수열

읽고 말하기 수열 - 나무위키

 

Run-length Encoding

개미 수열의 방법을 이해했다면 Run-length Encoding에 대해 이해하는 것은 어렵지 않다. 런 길이 부호화라고도 불리는 이 개념은 간단한 비손실 압축 방법으로 문자열을 저장할 때 컴퓨터에 메모리를 압축하여 저장하고자 사용한다.

예를 들면 아래와 같은 내용(12개의 W 1개의 B ....)

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Run-length Encoding을 통해 압축하면 12WB12W3B24WB14W 라는 값을 얻게 된다.

이와 같이 개미 수열과 아주 닮아 있고 알고리즘 문제 어디선가 본 듯한 내용을 가지고 있다.

 

그렇다면 두 개념을 이용해 개미 수열을 완성하고자 한다면 어떤 개념을 사용해야 할까 두 가지를 이용할 수 있다. 단순히 이전 문자와 같다면 그 수들의 길이를 저장했다가 다른 수가 나올 때 이전 내용을 수정하고 넘어가는 방식과 정규표현식을 이용하여 수정하는 방법이다. 전자의 경우 생각보다 긴 코드를 작성해야 한다. 그래서 정규표현식을 이용하여 이전 수들을 찾고 이를 Run-length Encoding 방식으로 표현하는 코드를 작성했다.

 

개미 수열 구현

소스코드

const arr = ["1"];
const regPractice = (n) => {
  for (let i = 1; i < n; i++) {
    const regExp = /(.)\1*/g;
    const result = arr[i - 1]
      .match(regExp)
      .reduce((a, b) => a + `${b.length}${b.slice(0, 1)}`, "");
    arr.push(result);
  }
};
regPractice(5);
console.log(arr.at(-1)); //111221

정규표현식에 대해 학습하며 단순히 문자를 검색하는 것이 전부가 아닌 추출과 대체를 편하게 할 수 있다는 점이 매력적이었습니다.

코드에 대해 설명하자면 시작은 항상 1로 배열에 값을 넣어두고 이전 값들을 활용하여 현재 인덱스에 값을 추가해야 하므로 n 값을 파라미터로 받아 n번째까지 개미 수열을 만드는 코드입니다.

정규표현식의 내용을 살펴보면 (.) 모든 단어나 수를 캡처하고 \1* 한번 이상 반복되는 모든 수들을 캡처하여 reduce를 통해 캡처된 숫자의 길이 + 해당 숫자로 표현하여 모두 붙여주고 배열에 넣어주면 구현이 가능하다.

 

해당 로직을 구현하는 것은 어렵지 않지만 정규표현식을 활용하는 방법을 모른다면 시간이 더 오래 걸릴 것 같다. 모든 정규표현식을 기억할 순 없겠지만 어떠한 방식으로 접근해야 하는지 알게 된 시간이었다.

 

참고

https://rubular.com/

Rubular