LeetCode알고리즘 Maximum Matrix Sum

오늘은 1975문제를 풀어보겠습니다.
중간 난이도며 43.9%의 성공률을 보이고 있네요.

 

문제를 살펴봅시다.

n x n 정수 행렬이 주어지고 
행렬의 인접한 두 요소를 선택해 각각에 -1을 곱하는 연산을 마음껏 할 수 있습니다. 
(단 border를 공유하는 경우에만 인접하다고 간주됩니다.)
그렇게 만든 행렬 요소의 합이 최댓값이 된다면 리턴하면 됩니다.

 

예시를 봅시다.

1번 예시:
[1, -1] 
[-1, 1] 
첫 번째 행에 -1을 곱해줍니다.  
[-1, 1] 
[-1, 1] 
다음 첫 번째 열에 -1을 곱해줍니다.
[1, 1] 
[1, 1] 
모든 원소의 합은 4가 되고 최댓값이 됩니다.

2번 예시:
[1 ,2, 3]
[-1, -2, -3]
[1, 2, 3]
두 번째 행에 마지막 두 원소에 -1을 곱해줍니다.
[1 ,2, 3]
[-1, 2, 3]
[1, 2, 3]
모든 원소의 합은 16이 되고 최댓값이 됩니다.

 

사실 규칙도 눈치 못 채고 계속 시도하다가 틀렸는데 여기에도 규칙이 있더라고요 :)

규칙이 뭐냐면?
행렬에 포함된 음수 원소의 개수가 짝수면? 모든 값이 양수로 바뀔 수 있기 때문에 모든 원소의 절댓값의 합을 리턴하면 되고
행렬에 포함된 음수 원소의 개수가 홀수면? 한 원소를 제외한 모든 값이 양수로 바뀔 수 있기 때문에 모든 원소의 절댓값의 합을 구하고 절댓값이 가장 작은 값 두배를 빼주고 리턴하면 됩니다.
ㅇㅇ?

 

즉 1번 예시의 경우 행렬에 포함된 음수 원소의 개수가 2개로 짝수이니 최대로 만들 수 있는 원소들의 합은 모든 원소 절댓값을 더한 값입니다. (4)
[1, -1] 
[-1, 1]에서
음수 원소 개수가 (-1, -1) 2개고
모든 절댓값을 다 더한 값이 4인데
행렬에 포함된 음수 원소의 개수가 짝수니까 그대로 4가 정답이 됩니다.

2번 예시의 경우 행렬에 포함된 음수 원소의 개수가 3개로 홀수니 최대로 만들 수 있는 원소들의 합은 모든 원소 절댓값을 더하고 (18) 절댓값이 가장 작은 값(1)의 두배를 빼주면 됩니다. (18 - 2 = 16)
[1, 2, 3]
[-1, -2, -3]
[1, 2, 3]에서
음수 원소 개수가(-1, -2, -3) 3개고
모든 절댓값을 다 더한 값이 18인데
행렬에 포함된 음수 원소의 개수가 홀수니까 절댓값이 가장 작은 수의 두배 빼줍니다. 
여기서는 1의 절댓값이 가장 작고 1의 두배를 빼주면 18 - 2한 값 16이 정답이 됩니다.

Q절댓값이 가장 작은 값으로 선택해서 뺀 이유는?
A우리는 최댓값을 만들어 리턴해야 하기 때문.

Q마지막에 두배를 뺀 이유는?
A내가 더해야하는 값들 -1, 2, 3 이 있다고 가정해봅시다.  = 4
절대값을 다 더하면 1 + 2 + 3이 되겠죠? = 6
그러니 (1 + 2 + 3) - (1 * 2)를 해줘야 음수가 더해진 값이 됩니다. = 6 - 2 = 4
즉 음수로 유지되어야 하는 값도 절댓값으로 더해졌으니 그 값은 두배로 빼줘야 함.

 

코드로 살펴봅시다.
n은 행렬의 크기를 나타내고
minimum은 절댓값이 가장 작은 값을 넣어주기 위한 변수고 
ans는 정답을 위한 변수고
negative는 행렬에 포함된 음수 원소를 카운팅 하기 위한 변수입니다.

func maxMatrixSum(_ matrix: [[Int]]) -> Int {
    let n = matrix.count
    var minimum = Int.max
    var ans = 0
    var negative = 0

    for i in 0..<n {
        for j in 0..<n {
            if matrix[i][j] < 0 {
                negative = negative + 1
            }
            ans = ans + abs(matrix[i][j])
            minimum = min(minimum, abs(matrix[i][j]))
        }
    }
    
    if negative % 2 == 0 {
        return ans
    } else {
        return ans - ( 2 * minimum)
    }
}

일단 이중 for loop를 돌면서 음수 원소의 개수를 카운팅하고
ans에 각 원소의 절댓값을 더해주고
minimum에 원소의 절댓값이 가장 작은 값을 넣어줍니다.
그리고 규칙에 따라 행렬에 포함된 음수 원소의 개수 짝수면 그대로 절댓값의 합 ans를 리턴하고
홀수면 절댓값의 합 ans에 가장 작은 절댓값 minimum 두 배를 빼주고 리턴합니다.

 

제출

어렵다 어려워