[C++] LeetCode : Count and Say

Question

COUNT and SAY 시퀀스는 재귀 공식으로 정의된 일련의 숫자 문자열이다.

Countandsay (1) = "1"
Countandsay (N)는 Countandsay (N-1)의 숫자 문자열을 "말하는"방식으로, 다른 숫자 문자열로 변환된다.

 

쉽게 말해 Countandsay (n)은 Countandsay (n-1) 을 읽어 반환하는 것인데, 읽는 방식은 아래와 같다.  

Countandsay (1) = "1"

Countandsay (2) = Countandsay (1) 은 1개의 1 = "11"

Countandsay (3) = Countandsay (2) 은 2개의 1 = "21"

Countandsay (4) = Countandsay (3) 은 1개의 2 , 1개의 1 = "1211"

Countandsay (5) = Countandsay (4) 은 1개의 1 , 1개의 2 , 2개의 1  = "111221"

이런 식으로 반복된다.

양의 정수 n이 주어지면 count-and-say s의 n 번째 항을 반환하는 문제이다.

 

제약사항

• n은 최소 1 최대 30이다.

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

  여느 규칙이 없고 1부터 차례대로 만들어야 하기 때문에, 만들어지는 가장 긴 문자열을 s라 하였을 때 O(ns)이다.

 

고려사항

1. 1일 경우

---

 

Solution1 - 1부터 차례로 만들어 반환

class Solution {
public:
    string process(string s) {
        string ret;
        char c; int count;
        for (int i = 0; i < s.length();) {
            count = 0;
            c = s[i];
            while (c == s[i]) {
                count++; i++;
            }
            ret += count + '0';
            ret += c;
        }

        return ret;
    }

    string countAndSay(int n) {
        string s[31];
        s[1] = "1";

        for (int i = 2; i <= n; i++) {
            s[i] = process(s[i - 1]);
        }

        return s[n];
    }
};

• Time complexity : O(ns) // s는 가장 긴 문자열
• Space Complexity : O(n) // 각 문자열을 저장해놓는 공간

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/4153/

Explore - LeetCode