[프로그래머스] Lv.2 롤케이크 자르기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/132265
• 🔑 누적합을 두 번 사용
  • 왼쪽에서 오른쪽으로 누적합 (li1)
  • 오른쪽에서 왼쪽으로 누적합 (li2)
  • li1[i] == li2[i+1] 이면 answer 1 증가

 

def solution(topping):
    answer = 0
    
    dic1 = {}
    dic2 = {}
    for t in topping:
        dic1[t] = False
        dic2[t] = False
        
    li1 = [0] * len(topping)
    li2 = [0] * len(topping)
    li1[0], li2[-1] = 1, 1
    dic1[topping[0]], dic2[topping[-1]] = True, True
    
    for i in range(1, len(topping)):        # 왼쪽 -> 오른쪽 누적합
        if dic1[topping[i]]:
            li1[i] = li1[i-1]
        else:
            li1[i] = li1[i-1] + 1
            dic1[topping[i]] = True
            
    for i in range(len(topping)-2, -1, -1): # 오른쪽 -> 왼쪽 누적합
        if dic2[topping[i]]:
            li2[i] = li2[i+1]
        else:
            li2[i] = li2[i+1] + 1
            dic2[topping[i]] = True
            
    for i in range(len(topping)-1):
        if li1[i] == li2[i+1]:
            answer += 1
    
    return answer