[LeetCode] 481. Magical String

문제 출처: https://leetcode.com/problems/magical-string/

Magical String - LeetCode

 

문제

마법의 문자열 s는 오직 1과 2로 구성되며, 다음의 규칙을 따른다:

• 문자열 s가 1과 2의 연속 발생 빈도를 연결했을 때, 자기 자신과 동일한 문자열이 라면 마법의 문자열이다.

 

s의 처음 몇 개의 원소는 s = "1221121221221121122……"이다. 만약 s 에서 연이은 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 ......"이다. s의 발생 빈도의 시퀀스가 s와 동일하다는 것을 확인할 수 있다.

 

정수 n이 주어지면, 마법의 문자열 s의 n개의 원소 중 1의 수를 반환하라.

 

예제

Input: n = 6
Output: 3

Explanation: The first 6 elements of magical string s is "12211" and it contains three 1's, so return 3.

 

풀이

마법의 문자를 만드는 과정을 순차적으로 살펴보면 다음과 같다.

         s(마법의 문자열)                          freq(빈도수)
0        1                                        1
1        1    22                                  1    2
2        1    22    11                            1    2    2
3        1    22    11    2                       1    2    2    1
4        1    22    11    2    1                  1    2    2    1    1
5        1    22    11    2    1    22            1    2    2    1    1    2

나열된 케이스를 보면 빈도수를 통해 문자열 s를 생성할 수 있다는 것을 알 수 있다. 문자 1과 2를 번갈아 가면서 빈도수만큼 해당 문자를 반복해주면 된다. 예를 들어, 빈도수가 1221이라면, s = "122112"가 된다.

 

문제에서 마법의 문자 정의에 따라서 s와 freq는 같기 때문에, s를 조금 더 긴 s를 얻기 위한 freq로 활용하여 확장된 s를 얻을 수 있다.

let s = '122';
while (s.length < n) {
    let nextS = '';
    let char = '1';
    for (let i = 0; i < s.length; i++) {
        nextS += char.repeat(Number(s[i]));
        char = preChar == '2' ? '1' : '2';
    }
}

이 과정을 다음과 같이 최적화할 수 있다. 현재 s를 만드는 구간만큼 건너 뛰어 반복 횟수를 줄이고자 했다.

 

예를 들어, 122는 빈도수 12를 s로 바꾼것이다. 그렇다면 122를 빈도수로 취급했을 때, s에 반영되지 않은 것은 마지막에 위치한 숫자 2, 12'2'이다. 이를 반영하면 s = "12211"이 된다.

 

이와 같은 방식으로 s를 확장하도록 하면 다음과 같은 코드가 된다.

let s = '122';
let idx = 2;
while (s.length < 2) {
    const char = s[s.length-1] == '1' ? '2' : '1';
    s += char.repeat(Number(s[idx]));
    idx += 1;
}

이렇게 만들어진 s에서 앞 n개의 원소에 대해서 1 개수를 세는 것으로 답을 도출할 수 있다.

let ans = 0;
for (let i = 0; i < n; i++) {
    ans += s[i] == '1' ? 1 : 0;
}
return ans;

 

Github: 481.js

opwe37/Algorithm-Study