[Golang으로 도전하는 Leetcode] Ways to Make a Fair Array

오늘 풀 문제는 Ways to Make a Fair Array라는 문제이며

링크는 leetcode.com/problems/ways-to-make-a-fair-array/입니다

이 문제의 설명은 아래와 같습니다

첫째로 모든 배열의 원소들을 빼면서 그 뺀 뒤의 홀수번째 원소들의 합과 짝수번째 원소들의 합이 같으면 fair하다

같지않으면 not fair하다 합니다

둘째로 구하는 값은 fair할 때 count를 하여 전체 배열의 원소들을 각각 다 뺐을 때의 그 count의 합을 구하는 문제입니다

 

저는 prefix sum을 사용해서 추가로 두 개의 배열을 더 만들어서 각각의 원소마다 짝수 원소들의 prefix sum, 홀수 원소들의 prefix sum을 구했습니다

지정한 원소가 빠졌을 때 그 뒤의 짝수 원소들은 홀수 원소들로 바뀌고 홀수원소들은 짝수원소들로 바뀌는 걸 이용하였습니다

prefix sum의 차이를 이용해 전체 짝수 원소들의 합에서 지정한 원소까지의 짝수 원소들의 합을 빼면 지정한 원소 뒤의 짝수 원소들의 합을 구할 수 있습니다.

위의 구한 합들은 이제 지정한 원소가 빠지게 되므로 짝수 원소들의 합이 아닌 홀수 원소들의 합으로 바뀌게 됩니다

이 홀수 원소들의 합과 현재 지정된 원소까지의 홀수 원소들의 합을 더하면 지정된 원소가 빠졌을 때의 홀수 원소들의 합을 구할 수 있게 됩니다

짝수원소들의 합도 똑같은 방법으로 구하면 됩니다

코드는 아래와 같습니다

func waysToMakeFair(nums []int) int {
    length := len(nums)
    odd_sum := 0
    even_sum := 0
    result := 0
    var odd_sum_list []int = make([]int, length)  
    var even_sum_list []int = make([]int, length)  
    for index, num := range nums {
        if(index%2 == 1){
            odd_sum += num
        }else{
            even_sum += num
        }
        odd_sum_list[index] = odd_sum
        even_sum_list[index] = even_sum
    }
    
    for index, _ := range nums {
        current_back_odd_sum := (even_sum - even_sum_list[index])
        current_back_even_sum := (odd_sum - odd_sum_list[index])    

        if(index> 0){
            if(current_back_odd_sum + odd_sum_list[index - 1] == current_back_even_sum + even_sum_list[index - 1]){
                result +=1
            }
            
        }else{
            if(current_back_odd_sum == current_back_even_sum){
                result +=1
            }
        }
    }
    return result
}

 

읽어주셔서 감사합니다