LeetCode -38. Count and Say

이영규·2023년 2월 19일
알고리즘

leet-code

목록 보기
1/1

문제 : https://leetcode.com/problems/count-and-say/

문제 이해

재귀적으로 연속되는 숫자의 개수를 세는 문제이다.
연속된 경우에만 카운트하는 걸 주의해야 한다. 나도 처음에는 전체 문자열에서의 숫자로 착각했었다.

주어진 숫자를 앞에서부터 순서대로 "연속된 숫자의 개수 + 연속된 숫자" 이렇게 2자리의 문자열로 바꿔나간다.

예를들어 "222334552" 가 주어진다면
처음에 2가 연속 3개 있으므로 32
그 다음 3이 연속 2개 있으므로 23
4가 1개 있으므로 14
5가 2개 있으므로 25
2가 1개 있으므로 12
합쳐서 "3223142512"가 된다.

다만 이 문제는 특정 숫자가 주어졌을 때 그 숫자를 문자열로 변경한 값을 리턴하는 게 아니라,
1번째 문자열이 "1" 이라고 가정하고,
n 번째 문자열이 (n-1) 번째 문자열을 변경한 값일 때,
주어진 n 에 대한 문자열을 응답해야 한다.

여기서 재귀의 개념이 사용된다.

해결 방법

문제 해결은 간단하다.

  1. 특정 숫자가 주어졌을 때, 그걸 규칙에 따라 문자열로 바꾸는 메서드를 정의한다.
  2. 해당 메서드를 재귀적으로 호출한다.(종결조건은 n=1 일때 "1"을 응답하는 것이다.)

한 단계씩 나아가보자.

1. 특정 숫자가 주어졌을 때, 규칙에 따라 문자열로 바꾸는 메서드를 정의한다.

나는 문제해결을 위해 "양방향 큐"를 생각했다.
양방향 큐에 "숫자와 갯수를 저장할 수 있는 객체"를 넣어
아래와 같은 절차를 통해 문제를 해결할 수 있다.

  • 문자열(숫자)을 순회하며 다음의 절차를 반복한다.
  • 현재 문자열을 "now" 라고 하자.
  • 양방향 큐의 가장 마지막에 들어있는 객체를 꺼낸다. 해당 객체를 {"last", count} 라고 하자.
    • 이 객체는 숫자("last")와 갯수(count)를 저장하고 있다.
  • "now" == "last" 라면 count를 +1 한다.
  • "now" != "last" 라면 큐에 {"now", 1} 를 넣는다.
  • 큐가 비어있다면 비교 없이 {"now", 1} 를 넣는다.

객체는 직접 정의해도 되고, 페어 자료구조를 사용해도 된다.
코드로 나타내면 아래와 같다.

    private fun convert(say: String): String {
        val queue = mutableListOf<Counter>()    // 리스트를 양방향 큐처럼 사용

        // 순회하며 양방향 큐를 규칙에 따라 채운다.
        for (c in say) {
            val now = Character.getNumericValue(c)
            // 큐가 비어있거나 last != now 라면 큐에 now(1)를 넣는다.
            if (queue.isEmpty() || queue.last().num != now) {
                queue.add(Counter(now, 1))
            } else {    // last == now 라면 last 의 count 를 추가한다.
                queue.last().count++
            }
        }

        return queue.asSequence()
            .map { counter -> counter.toString() }
            .fold("") { ans, nxt -> ans + nxt } // 문자열을 이어붙인다.
    }

    class Counter(
        val num: Int,
        var count: Int
    ) {
        override fun toString(): String {
            return this.count.toString() + this.num.toString()
        }
    }

2. 해당 메서드를 재귀적으로 호출한다.(종결조건은 n=1 일때 "1"을 응답하는 것이다.)

그러면 이제 해당 메서드를 재귀 호출 하면 된다.

    fun countAndSay(n: Int): String {
        if (n == 1) {
            return "1"
        }
        return convert(countAndSay(n - 1))
    }

전체 코드는 아래의 링크에서 확인할 수 있다.
https://github.com/yglee8048/leet-code/blob/master/src/main/kotlin/P38_Count_and_Say.kt

시간 복잡도

이제 시간 복잡도를 계산해보자.

일단 convert 함수의 시간 복잡도는 아래와 같다.

  • 주어진 문자열의 길이를 n, 연속된 문자열을 합친 큐의 길이를 m 이라고 하면, 각각 순회하므로
    • O(n + m)
  • 이 때 m <= n 이므로
    • O(n + m) <= O(2n) = O(n)

이제 재귀 함수의 시간 복잡도를 생각해보자.
아래와 같은 점화식을 생각해볼 수 있다.

  • T(n) = T(n-1) + L(n-1)
    • T(n) = n번째 수행시간
    • L(n) = n번째 문자의 길이

이 때, T(1) = 1 이므로, T(2) = 1 + L(1) 이다.
결과적으로 아래와 같다.

  • T(n) = 1 + L(1) + ... + L(n-1) = = L(1) + ... + L(n-1)
  • T(n) = (n-1) * L
    • 이 때 L 은 L(n) 의 최대 길이

따라서 시간 복잡도는 O(nL) 이다.

profile
이영규
더 빠르게 더 많이 성장하고 싶은 개발자입니다

0개의 댓글