파이썬으로 인코딩이 고유한 이진 문자열을 나타내는지 확인하는 방법

크기가 k인 이진 문자열의 인코딩을 나타내는 배열 nums가 주어졌을 때, 해당 인코딩이 이진 문자열을 유일하게(unique) 결정하는지 확인해야 하는 문제를 살펴보겠습니다.

여기서 인코딩은 연속된 1의 개수들을 의미하며, 각 그룹은 하나의 0으로 구분됩니다. 즉, 인코딩 [a1, a2, ..., an]은 'a1개의 1, 0 한 개, a2개의 1, 0 한 개, ..., an개의 1' 형태의 문자열에 해당합니다.

문제 이해하기

예를 들어 입력이 nums = [4, 2, 3]이고 k = 11이라고 가정해 봅시다. 이 경우 출력은 True가 됩니다. 왜냐하면 '11110110111'과 같은 길이 11의 이진 문자열이 존재하고, 이 인코딩으로부터 정확히 하나의 문자열만 만들어질 수 있기 때문입니다.

접근 방법

핵심 아이디어는 매우 간단합니다. 인코딩으로 표현되는 전체 문자열의 길이를 계산해서 k와 비교하는 것입니다.

• 먼저 nums에 있는 모든 요소(연속된 1의 개수)의 합을 구합니다.
• 각 그룹 사이에는 반드시 하나의 0이 들어가므로, 구분자 0의 개수는 (배열 크기 - 1)개입니다. 이 값을 더해줍니다.
• 계산된 총 길이가 k와 같으면 True, 아니면 False를 반환합니다.

만약 총 길이가 k보다 작거나 크다면, 해당 인코딩으로 길이 k의 유효한 이진 문자열을 유일하게 표현할 수 없습니다.

구현 예제

def solve(nums, k):
    total = sum(nums)          # 모든 1의 개수 합산
    total += len(nums) - 1     # 그룹 사이의 0 개수 추가
    return total == k

nums = [4, 2, 3]
k = 11
print(solve(nums, k))

입력

[4, 2, 3], 11

출력

True

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 nums 배열의 길이로, 배열의 합을 한 번 계산하기 때문입니다. 공간 복잡도는 추가 저장 공간을 사용하지 않으므로 O(1)입니다.

이처럼 단순한 수학적 계산만으로 인코딩의 유효성을 빠르게 판별할 수 있습니다.