문제 소개
2차원 행렬과 여러 개의 셀 인덱스가 주어졌다고 가정해 보겠습니다. 셀 인덱스는 (i, j) 형태로 표현되며, 여기서 i는 행(row), j는 열(column)을 의미합니다. 이때 주어진 각 셀 인덱스 (i, j)마다, 해당 i번째 행과 j번째 열에 속한 모든 요소를 제외한 나머지 행렬 요소들의 합을 구해야 합니다.
예를 들어 다음과 같은 3x3 행렬이 있다고 해보겠습니다.
| 2 | 2 | 3 |
| 4 | 5 | 7 |
| 6 | 4 | 3 |
셀 인덱스가 [(0, 0), (1, 1), (0, 1)]로 주어진다면, 결과는 [19, 14, 20]이 됩니다.
결과 검증
- (0, 0): 0번째 행과 0번째 열을 제외하면 남는 요소는 5, 7, 4, 3 → 합계 19
- (1, 1): 1번째 행과 1번째 열을 제외하면 남는 요소는 2, 3, 6, 3 → 합계 14
- (0, 1): 0번째 행과 1번째 열을 제외하면 남는 요소는 4, 7, 6, 3 → 합계 20
해결 접근 방법
이 문제를 해결하기 위해 다음과 같은 단계를 따릅니다.
- 인덱스 배열(ind_arr)의 크기를 n에 저장합니다.
- 결과를 담을 빈 리스트 ans를 생성합니다.
- n번 반복하면서 각 셀 인덱스에 대해:
- 합계를 저장할 변수 Sum을 0으로 초기화합니다.
- 현재 인덱스의 행 값(row)과 열 값(col)을 추출합니다.
- 행렬의 모든 위치 (j, k)를 순회하면서, j가 row와 같지 않고 k가 col과도 같지 않은 경우에만 해당 요소를 Sum에 더합니다.
- 완성된 Sum을 ans 리스트의 끝에 추가합니다.
- 모든 반복이 끝나면 ans를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작을 확인할 수 있습니다.
def show_sums(mat, ind_arr):
n = len(ind_arr)
ans = []
for i in range(0, n):
Sum = 0
row = ind_arr[i][0]
col = ind_arr[i][1]
for j in range(0, len(mat)):
for k in range(0, len(mat[0])):
if j != row and k != col:
Sum += mat[j][k]
ans.append(Sum)
return ans
mat = [[2, 2, 3], [4, 5, 7], [6, 4, 3]]
ind_arr = [(0, 0), (1, 1), (0, 1)]
print(show_sums(mat, ind_arr))입력
mat = [[2, 2, 3], [4, 5, 7], [6, 4, 3]] ind_arr = [(0, 0), (1, 1), (0, 1)]
출력
[19, 14, 20]
시간 복잡도 분석
각 셀 인덱스마다 행렬 전체를 한 번씩 순회하므로, 시간 복잡도는 O(n × m × q)입니다. 여기서 m은 행의 수, 행렬의 열 수를 곱한 크기, q는 쿼리(셀 인덱스)의 개수입니다. 행렬이 매우 크고 쿼리가 많다면, 누적합(prefix sum) 기법을 활용해 각 행과 열의 합을 미리 계산해 두면 성능을 크게 개선할 수 있습니다.