[PS, Algorithm] - 롤케이크 자르기 (코딩테스트 연습, LEVEL 2)

📒문제

📌코드

from collections import Counter
from collections import defaultdict

def solution(topping):
    d1 = defaultdict(int)
    d2 = Counter(topping)
    
    answer = 0
    for i in range(len(topping)):
        d1[topping[i]] += 1
        d2[topping[i]] -= 1
        
        if d2[topping[i]] == 0: d2.pop(topping[i])
        if len(d1) == len(d2): answer += 1
        
    return answer

topping의 길이가 백만개를 넘으므로, 필연적으로 O(N) 시간복잡도 이하로 코드를 짜야지만 통과하겠다고 생각했다.

처음 생각했던 방식은 커서를 놓고 커서 기준으로 배열을 잘라 set을 써서 set의 길이가 같다면 공평하게 나뉜것으로 간주하는 알고리즘을 짜보려 했지만, 생각해보니 set을 계속 초기화하는 과정에서 시간초과가 날수도 있겠다고 판단했다.

따라서 set을 계속 초기화하는 대신, 커서가 움직일때마다 왼쪽 배열에는 커서가 가리키는 값을 더하고 오른쪽 배열에는 커서가 가리키는 값을 빼는 방식으로 알고리즘을 짜서 O(N)에 해결할 수 있도록 코드를 구성했다.