[codeforce] D. Non-zero Segments

문제 출처 

https://codeforces.com/problemset/problem/1426/D

Problem - 1426D - Codeforces

 

풀이 

n = int(input())
nums = list(map(int, input().split()))
# print(nums)

acc_sum = [0] * 200001 # 누적합 위한 공간 
sub_acc_map = {}
sub_acc_map[0] = 'exists'  # 합이 0 인 것을 찾기 위해 초기화 

result = 0 

for i in range(n):
    acc_sum[i] = nums[i];
    
    if i > 0 :
        acc_sum[i] = acc_sum[i] + acc_sum[i - 1]
   
    if acc_sum[i] in sub_acc_map :
    # if acc_sum[i] == 0:
        print(i, ' : ' , acc_sum[i], ' - ', sub_acc_map)
        result += 1; 
        sub_acc_map.clear()
        sub_acc_map[acc_sum[i]] = 'exists' 
        
    sub_acc_map[acc_sum[i]] = 'exists' 


print(result)

 

아래 예시에서, `acc_sum[i] in sub_acc_map :` 이 조건을 조금 더 자세히 설명하면, 이렇게 된다. 

4
1 -5 3 2

i = 0	i = 1	i = 2	i = 3
acc_sum = [1] suc_acc_map = { 0 : exists, 1 : exists }	acc_sum = [1, -4] suc_acc_map = { 0 : exists, 1 : exists, -4 : exists, }	acc_sum = [1, -4, -1] suc_acc_map = { 0 : exists, 1 : exists, -4 : exists, -1 : exists }	acc_sum = [1, -4, -1, 1] suc_acc_map = { 1 : exists }

 

이렇게 왜 그런지 뭔가 내가 이해 못하는 게 있는가 싶었는데, 그냥 부분합이 0인것을 구하고자 했을때, 쓰는 알고리즘인 것 같았다. 

 

 

https://wikidocs.net/193295

문제 2. 합이 0인 부분 배열 중 가장 긴 것을 찾아라.

 

chatgpt도 그렇다고 한다...