Leetcode : Contiguous Array
문제 링크
글의 목적
문제를 복습해서 풀다가 해결 방안이 계속 떠오르지 않아 작성했습니다.
문제의 유형을 이해하는게 아니라 기억속의 해결방안을 재현하는 수준에 그쳤기 때문이라고 생각합니다.
이 글은 이러한 문제 유형을 계속해서 풀지 못하는 이유를 글로 정리하여 해결 원리를 이해하는것을 목표로 합니다.
요약
배열을 순회할 때 일정한 규칙이 생성되지 않으므로 현재 pointer 대비 nums의 0과 1의 개수를 기록하여 배열의 길이를 구할 수 있습니다.
0의개수 = 0
1의개수 = 1
해시테이블 = {0: -1}
answer = 0
for 현재포인터 in nums:
0의개수 += 1 if nums[현재포인터] == 0 else 0
1의개수 += 1 if nums[현재포인터] == 1 else 0
개수차이 = 0의개수 - 1의개수
if 개수차이 in 해시테이블: # -1 : 0이 더 많음, 1 : 1이 더 많음, 0 : 0과 1의 개수 동일
# (현재포인터 - 이전포인터 + 1)를 하면 배열의 길이가 나오는데 이전 포인터가 가리키는 원소를 제외하면 0과 1의 개수가 같아짐 따라서 현재포인터 - 이전포인터가 나옴
answer = max(answer, 현재포인터 - 해시테이블[개수차이])
else: # 새로운 개수차이가 있을 경우
해시테이블[개수차이] = 현재포인터
return answer
문제 개요
문제의 내용을 요약하자면 다음과 같습니다.
원소가
0과1로만 이루어진nums가 주어진다. 이때0과1의 개수가 같은contiguous subarray의 최대 길이를 구하는 코드를 작성해야 한다
문제 분석
1. contiguous subarray는 무엇인가
subarray는 array에서 원소의 값과 순서가 같은 부분 배열을 의미합니다. 이미 subarray 자체에 contiguous 의미가 내포하고 있으며, 의미를 강조하기 위한 표현으로 보입니다.
subarray자체는 연속성이 있기 때문에 for loop로 모든 subarray를 순회 할 수 있습니다.
조건에 맞는 subarray를 찾기 위해선 sliding-window , hashmap을 사용하여 해결할 수 있을것으로 보입니다.
2. two-pointer 전략을 사용할 수 있을까?
two-pointer은 사용 가능할까요? 결론부터 말씀드리자면 그렇지 않습니다.
subarray를 찾으려면 원소 순서까지 같아야 하고 포인터 이동 전략이 명확해야 하는데 주어진 nums는 원소들 끼리의 규칙이 없기 때문입니다.
2. sliding-window 전략을 사용할 수 있을까?
sliding-window 전략을 사용할 때 window-size는 0과 1의 개수가 같은 subarray를 만족해야 합니다.
그렇다면 어떻게 0과 1의 개수가 같음을 만족할 수 있을까요? 아래와 같이 현재 window가 (right - left + 1) // 2조건을 충족하면 되지않을까요?
left = 0
numberOfOne = 0
answer = 0
for right in range(len(nums)):
numberOfOne += nums[right]
if (right + 1) % 2 == 0:
while (right - left + 1) // 2 != numberOfOne:
if nums[left] == 1:
numberOfOne -= 1
left += 1
answer = max(answer, right - left + 1)
return answer
그러나 sliding-window는 현재 식별한 포인터에서 정답을 확인할 수 없습니다.
왜냐하면 nums는 포인터를 증가시킬때 마다 그 성질이 일관된 형태로 변화하지 않기 때문입니다.
nums = [0, 0, 0, 1, 1 ,1]일 경우 sliding-window를 적용하면 중간의 right = 3일때 left가 두칸 이동합니다.
이런 상황에서 경우의 수를 놓치게 되어 본래 정답인 6이 나오지 않습니다.
3. hashmap으로 현재 포인터를 기준으로 값의 위치를 기록하기
hashmap을 활용하여 이전 pointer들의 0과 1의 개수를 기록하면서 현재 pointer에서 최적의 값을 구하면 누락된 경우의 수를 놓치지 않고 해결할 수 있습니다.
그렇다면 0과 1의 개수를 어떻게 효율적으로 파악가능할까요?
직관적으로 확인하는 방법으로 0의 개수와 1의 개수의 차이를 기록해 나갑니다. 형태는 {개수차이:index} 형태로요.
0의 개수와 1의 개수의 차이가 0일 경우 1과 0의 개수가 같아지므로 subarray를 만족하게 됩니다.
이 값은 어떻게 계산할 수 있을까요? 0부터 현재 포인터까지 길이는 현재포인터 - 0 + 1입니다. 일단 {0: 0}을 기록해둡시다.
현재 포인터 기준으로 어떻게 해시테이블을 활용하여 0의 개수와 1의 개수가 같아지는 index를 구할 수 있을까요?
current를 기준으로 똑같은 개수차이를 가진 이전 포인터를 찾아서 현재 포인터에서 아래와 같이 빼면 됩니다.
그 이유는 current에서 똑같은 개수 차이가 발생하고 이전과 똑같은 차이가 났던 index를 제외시키면 1의 개수와 0의 개수가 같아지기 때문입니다.
그현재 포인터에서 0과 1의 개수가 같아진다면 current까지의 배열 길이이므로current - 0 + 1이 되야합니다.
따라서 {0 : 0}을 기록하는 것이 아닌 {0 : -1}로 기록해야 합니다.
최종 코드
hashTable을 이용하여 해당 문제의 해결방안은 아래와 같이 작성할 수 있습니다.
각 index별로 subarray의 조건을 활용할 수 있는 정보를 기록해야 해결할 수 있는 문제였습니다.
hashTable = {0 : -1}
numberOfZero = 0
numberOfOne = 0
answer = 0
for current in range(len(nums):
numberOfZero += 1 if nums[current] == 0 else 0
numberOfOne += 1 if nums[current] == 1 else 0
difference = numberOfZero - numberOfOne
if difference in hashTable:
answer = max(answer, current - hashTable[difference])
else:
hashTable[difference]
return answer