latentspace.world

이번주 월요일과 화요일에는 개인 사정으로 다른 일을 했다. 오늘부터 문제를 다시 풀어보자.

문제

숫자로만 구성된 문자열 num이 주어진다. 길이는 n이다. 모든 인덱스 i(0 <= i < n)에 대해, 숫자 i가 num[i] 횟수만큼 문자열 num에 나타나는지 확인한다. 이 조건이 모든 인덱스에 대해 참이면 true를 반환하고, 그렇지 않으면 false를 반환한다.

예시

예시 1:

입력: num = "1210"
출력: true
설명:
num[0] = '1'. 숫자 0은 num에 1번 나타난다.
num[1] = '2'. 숫자 1은 num에 2번 나타난다.
num[2] = '1'. 숫자 2는 num에 1번 나타난다.
num[3] = '0'. 숫자 3은 num에 0번 나타난다.

예시 2:

입력: num = "030"
출력: false
설명:
num[0] = '0'. 숫자 0은 0번 나타나야 하지만, 실제로는 2번 나타난다.
num[1] = '3'. 숫자 1은 3번 나타나야 하지만, 실제로는 0번 나타난다.
num[2] = '0'. 숫자 2는 num에 0번 나타난다.

첫 번째 접근법: O(n²) 솔루션

처음에는 문자열을 순회하면서 갯수를 세는 간단한 접근법을 생각했다.

class Solution:
    def digitCount(self, num: str) -> bool:
        for i in range(len(num)):
            count = list(num).count(str(i))
            if count != int(num[i]):
                return False
        return True

이 솔루션은 간결하고 이해하기 쉽지만, 시간 복잡도는 O(n²)이다:

바깥 반복문은 n번 실행된다 (각 인덱스마다 한 번씩)
각 반복마다 count() 메서드가 전체 문자열을 순회한다 (n번의 연산)
총 시간 복잡도: O(n²)

두 번째 접근법: O(n) 솔루션

해시 맵(Python에서는 딕셔너리)을 사용하여 시간 복잡도를 O(n)으로 줄이는 더 효율적인 접근법을 생각해 보았다.

def digitCount(self, num: str) -> bool:
    counts = {}

    # 문자열에서 각 숫자의 출현 횟수를 세기 (O(n))
    for n in num:
        if n in counts:
            counts[n] += 1 # (O(1))
        else:
            counts[n] = 1 # (O(1))

    # 각 인덱스 i가 num[i]번만큼 나타나는지 확인 (O(n))
    for i in range(len(num)):
        if str(i) not in counts: # (O(1))
            counts[str(i)] = 0 # (O(1))
        if counts[str(i)] != int(num[i]): # (O(1))
            return False

    return True

최적화된 솔루션의 작동 방식

먼저, 문자열에서 각 숫자가 몇 번 나타나는지 추적하는 빈도 맵(counts)을 만든다.
1. 이는 O(n) 시간이 소요된다.
그런 다음, 각 인덱스 i를 반복하면서 숫자 i가 빈도 맵에 따라 정확히 num[i]번 나타나는지 확인한다.
1. 이 또한 O(n) 시간이 소요된다.
총 시간 복잡도는 O(n) + O(n) = O(n)이다.

두 접근법 비교

첫 번째 접근법:
- 장점: 공간 복잡도 O(1)
- 단점: 매 반복마다 전체 문자열을 스캔하므로 O(n²) 시간 복잡도를 가진다
두 번째 접근법 (해시 맵 사용):
- 장점: 전체 문자열을 한 번만 스캔하므로 O(n) 시간 복잡도를 가진다
- 단점: 공간 복잡도 O(n)

결론

입력 문자열의 길이 제한이 10개로 제한되어 있어 첫 번째 솔루션도 시간 복잡도 측면에서 그렇게 비효율적이라고 생각하지는 않는다.

만약 입력 길이가 매우 커진다면 두 번째 솔루션이 보다 효율적일 것이다.