문제 소개
매직 문자열(magical string)은 오직 '1'과 '2'로만 구성되며, 다음과 같은 독특한 규칙을 따르는 문자열입니다.
이 문자열이 '매직(magical)'이라 불리는 이유는, 문자열 안에서 연속으로 등장하는 '1'과 '2'의 개수를 순서대로 이어 붙였을 때 그 결과가 원래 문자열 자기 자신과 동일해지기 때문입니다.
매직 문자열 str의 첫 부분은 다음과 같습니다.
str = "1221121221221121122……"
문자열에서 연속된 '1'들과 '2'들을 그룹으로 묶어 보면 다음과 같습니다.
1 22 11 2 1 22 1 22 11 2 11 22 ……
그리고 각 그룹에 포함된 '1' 또는 '2'의 개수를 차례대로 나열하면 다음과 같습니다.
1 2 2 1 1 2 1 2 2 1 2 2 ……
위의 등장 횟수 수열이 곧 원래 문자열 자체와 일치한다는 것을 확인할 수 있으며, 이것이 매직 문자열의 핵심 성질입니다.
요구 사항
정수 num이 입력으로 주어졌을 때, 매직 문자열 str의 처음 num개 문자 중 '1'의 개수를 반환하는 함수를 작성해야 합니다.
예를 들어 함수의 입력이 다음과 같다면,
const num = 6;
출력은 다음과 같아야 합니다.
const output = 3;
출력 설명
매직 문자열의 처음 6개 문자는 "122112"이며, 이 안에는 '1'이 세 번 등장합니다. 따라서 결과값으로 3을 반환합니다.
구현 예시
const num = 6;
const magicalString = (num = 1) => {
let ind = 12;
let str = '1221121221221121122';
while(str.length < num){
const end = str.substring(str.length - 1) === '2' ? '1' : '2';
str = parseInt(str.substring(ind, ind + 1)) === 2 ? str + end + end : str + end;
ind++;
};
return (str.substring(0, num).match(/1/g)||[]).length;
};
console.log(magicalString(num));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
3
코드 동작 원리
이 코드는 이미 검증된 매직 문자열의 앞부분("1221121221221121122")을 초깃값으로 미리 준비해 두고, 요청한 길이에 도달할 때까지 문자열을 규칙에 맞게 확장하는 방식으로 동작합니다.
- 변수 str에는 매직 문자열의 앞 19글자가 저장되어 있습니다. 입력된 num이 이 길이보다 작거나 같으면 반복문 없이 즉시 답을 계산할 수 있습니다.
- 변수 ind는 문자열을 확장할 때 참조할 지시 숫자의 위치를 가리키는 포인터 역할을 합니다.
- 반복이 진행되는 동안 end 변수는 새로 추가할 문자를 결정합니다. 현재 문자열의 마지막 문자가 '2'라면 '1'을, '1'이라면 '2'를 추가하여 두 문자가 그룹 단위로 번갈아 나타나도록 만듭니다.
- ind 위치의 숫자가 2이면 해당 문자를 두 개 이어 붙이고, 1이면 하나만 추가합니다.
- 마지막으로 정규식 /1/g을 사용해 처음 num개 문자에서 '1'의 개수를 세어 반환합니다.