[알고리즘] 해시_방울 python

💡 풀이 참고 전 코드 (실패)

def solution(bell):
    answer = 0
    accumulate_bell = [0]
    for i in range(len(bell)):
        if bell[i] == 1:
            accumulate_bell.append(accumulate_bell[i+1-1]+1)
        else:
            accumulate_bell.append(accumulate_bell[i+1-1]-1)
    s, e = 0, 2
    while s < len(accumulate_bell) and e < len(accumulate_bell):
        if accumulate_bell[s] == accumulate_bell[e]:
            answer = max(answer, e-s)
            e += 1
        else:
            e += 1
        if e >= len(accumulate_bell) and s < e-2:
                s += 1
                e = (s + 2)
    return answer

사실 처음엔 아이디어도 떠올리기 어려웠다. 강의에서 제시한 아이디어 (초록방울일 경우 1, 빨간방울일 경우 -1을 해서 누적값이 같아질 떄의 최대 길이 구하기) 를 참고하고 짜봤지만, bell의 최대 길이가 1,000,000이라 테스트케이스 말곤 모두 시간초과가 났다.
while문 안에서 e, s의 값을 변경해서 시간초과가 난 것 같다.

💡 강사님 풀이

from itertools import accumulate

def solution(bell):
    coors_start = {}
    coors_end = {}
    for i, x in enumerate(accumulate([0] + [-1 if b == 1 else 1 for b in bell])):
        if x not in coors_start:
            coors_start[x] = i
        coors_end[x] = i
    return max(coors_end[x] - coors_start[x] for x in coors_end)

• 먼저 itertools의 accumulate 사용법을 알아야 할 것 같다.

from itertools import accumulate

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b = list(accumulate(a))
print(a)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(b)  # [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

• accumulate는 누적합을 뽑아준다.

같은 수의 길이를 구해주는 부분에서 시간초과를 해결하지 못했는데 강사님 풀이에선 이를 딕셔너리를 활용해서 풀었다.
start와 end 딕셔너리를 각각 만들어주고, start 딕셔너리는 초기 key값 한 번만, end 딕셔너리는 같은 key값이 나오면 업데이트 해준다.
key는 실제 누적 값이고, value는 인덱스 이다.
(최대 길이를 구하는 것이기 때문에 start는 가장 앞의 수, end는 가장 뒤의 수를 찾아야 하기 때문)

• 처음엔 for문 안에서 if x not in coors_start: 부분이 for문 안에 있어 O(N)보다 큰 시간복잡도를 가질 것이라 생각했지만, 아니었다. 딕셔너리의 key값을 찾는 연산(in)은 평균적으로 상수 시간에 수행된다.

✔️ 배운점

1️⃣ itertools의 accumulate로 누적합을 구할 수 있다.

2️⃣ 딕셔너리 내부에서 키의 존재 여부를 확인하는 연산(in 연산자)은 해시 테이블을 이용하여 평균적으로 상수 시간에 수행된다. (앞으로 리스트에서 같은 숫자의 인덱스를 찾을 땐 해시 테이블, 즉 딕셔너리 자료구조를 사용해보자!⭐️)