[Codeforces] 481. Magical String

https://leetcode.com/problems/magical-string/

Magical String - LeetCode

이 문제는 앞서 푼 문제의 다음 챌린지로 추천된 문제여서 풀게된 문제이다.

역시나 주어진 규칙을 곧이곧대로 받아들이는 것이 아니라, 규칙 내의 패턴을 활용해야 한다.

 

규칙

The string s is magical because concatenating the number of contiguous occrrences of characters '1' and '2' generates the string s itself.

 

여기서 해석을 잘해야 한다. 핵심적으로 봐야할 것은 itself이다.

s에서 연속되는 숫자가 등장하는 수를 기록한 것이 s 그 자체가 되어야한다는 뜻이다.

 

투포인터는 지금까지 한 배열이나 문자열에서 인덱스를 두 개로 두어 양 끝을 표시하는 방식으로 탐색을 하였다.

하지만 이번 문제에서는 하나의 문자열에서 각기 다른 것을 표시하는 방식으로 활용한다.

하나는 등장하는 연속된 수를 세기 이전의 인덱스, 수를 센 후의 인덱스를 표시한다.

 

class Solution {
public:
    int magicalString(int n) {
        int i = 2;
        string s = "122";
        while(s.length() < n){
            int cnt =  s[i] - '0';
            char num = 3 - (s.back()  - '0') + '0';
            for(int j = 0;j < cnt;j++) {
                s += num;
            }
            i++;
        }

        cout << s << endl;
        return count(s.begin(), s.begin() + n, '1');
    }
};