[LeetCode 풀이/python] 38. Count and Say (easy)

문제 설명: count-and-say 시퀀스는 아래와 같이 재귀적인 규칙에 의해 정의되는 숫자 문자열이다:

• countAndSay(1) = "1"
• countAndSay(n) 은 countAndSay(n-1) 결과인 숫자 문자열을 읽는(say) 방법으로서, 이를 또다른 숫자 문자열로 변환한 것이다.

어떤 숫자 문자열을 어떻게 읽는지(say) 정하기 위해서는, 연속된 동일한 숫자가 하나의 그룹을 이루도록 숫자 문자열을 최소한의 그룹으로 나눈 뒤, 각 그룹에 대해 숫자의 갯수와 숫자를 차례로 읽는다. 읽는 법을 숫자 문자열로 변환하기 위해, 갯수를 숫자로 바꾸고 각 읽는 법을 연결해 붙인다.

예를 들어, 숫자 문자열 "3322251" 의 변환 과정은 다음과 같다: two 3's, three 2's, one 5, and one 1 = 2 3 + 3 2 + 1 5 + 1 1 = "23321511"

 

(The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string "3322251": two 3's, three 2's, one 5, and one 1 = 2 3 + 3 2 + 1 5 + 1 1 = "23321511"

 

예시 1)

입력: n = 1  -->  출력: "1"

설명: 베이스 케이스에 해당

 

예시 2)

입력: n = 4  -->  출력: "1211"

설명: countAndSay(1) = "1" 

   ->  countAndSay(2) = say "1" = one 1 = "11" 

   ->  countAndSay(3) = say "11" = two 1's = "21" 

   ->  countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

 

제한 조건:

• 1 <= n <= 30

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • CountAndSay(n) 에서 읽을 대상이 되는 문자열 cand = CountAndSay(n-1) 을 앞에서부터 한 자리씩 읽어 나가되,
    • 직전에 읽은 숫자와 다른 숫자가 등장하면 해당 숫자를 num_digit 배열에 추가 & num_cnt 배열의 동일 인덱스에 +1
    • 연속된 숫자가 등장하는 경우 해당하는 num_cnt 만 업데이트
  • 불연속한 숫자가 등장 순서대로 저장된 num_digit 배열을 순회하며 숫자 -> count + 숫자 형태로 변환하여 저장

 

• 코드 구현

def countAndSay(n: int) -> str:
    if n == 1:
        return '1'
    else:
        num_digit = ['0']
        num_cnt = [0]
        cand = countAndSay(n-1)
        for num in cand:
            if num != num_digit[-1]:
                num_digit.append(num)
                num_cnt.append(1)
            else:
                num_cnt[-1] += 1

        for i, num in enumerate(num_digit):
            if i == 0: num_digit[i] = ''
            else:
                num_digit[i] = str(num_cnt[i]) + num

    return ''.join(num_digit)

 

• 결과
  • 재귀 매 스텝별로 주어진 문자열에 대해 linear 하게 탐색하는 방식은 시간 복잡도 상 optimal 한 접근인 것 같으나... 
  • 별도로 num_digit & num_cnt 배열을 만들어 저장하는 방식에서 메모리 효율이 떨어지는 것으로 보임
  • 파이썬 기본 라이브러리 itertools 의 groupby 함수를 활용하는 것도 하나의 방법인 듯...!