문제 소개
m × n 크기의 행렬과 정수 k가 하나 주어진다고 가정해 봅시다. 이때 행렬의 좌표 (a, b)에 해당하는 값은, i가 0부터 a까지, j가 0부터 b까지의 범위에 있는 모든 matrix[i][j] 요소들을 XOR한 결과값입니다. 우리가 구해야 할 것은 행렬의 모든 좌표 값들 중에서 k번째로 큰 값(1부터 시작하는 인덱스)입니다.
예를 들어 입력이 다음과 같다면,
| 5 | 2 |
| 1 | 6 |
k = 1일 때의 출력은 7이 됩니다. 좌표 (0, 1)의 값이 5 XOR 2 = 7로 계산되는데, 이것이 전체 좌표 값 중 가장 큰 값이기 때문입니다.
참고로 이 행렬의 네 좌표 값은 각각 (0,0)=5, (0,1)=7, (1,0)=4, (1,1)=0으로 계산되며, 내림차순으로 정렬하면 7, 5, 4, 0이므로 첫 번째로 큰 값은 7입니다.
해결 접근 방법
이 문제는 두 단계의 누적 XOR(prefix XOR) 연산과 상위 k개 값만 유지하는 딕셔너리를 활용해 효율적으로 해결할 수 있습니다.
- 행 방향 누적 XOR: 먼저 각 행에 대해 왼쪽에서 오른쪽으로 누적 XOR을 수행합니다.
- 열 방향 누적 XOR 및 값 집계: 각 열에 대해 위에서 아래로 누적 XOR을 적용하면 각 좌표의 최종 XOR 값이 완성됩니다. 동시에 딕셔너리(seen)에 각 값의 등장 횟수를 기록하고, 처리한 원소 수(count)가 k를 초과하면 딕셔너리에서 최솟값을 하나 제거하여 항상 상위 k개의 값만 유지합니다.
- 결과 반환: 마지막으로 딕셔너리에 남아 있는 값들 중 최솟값이 곧 k번째로 큰 값입니다.
알고리즘 단계
구체적인 절차는 다음과 같습니다.
- m := 행의 개수, n := 열의 개수로 설정
- i를 0부터 m-1까지 순회:
- j를 0부터 n-1까지 순회:
- j가 0이 아니면 matrix[i][j] := matrix[i][j] XOR matrix[i][j-1]
- j를 0부터 n-1까지 순회:
- seen := 빈 딕셔너리 생성
- count := 0으로 초기화
- i를 0부터 n-1까지 순회:
- j를 0부터 m-1까지 순회:
- j가 0이 아니면 matrix[j][i] := matrix[j][i] XOR matrix[j-1][i]
- seen[matrix[j][i]]의 개수를 1 증가
- count를 1 증가
- count > k이면:
- min_value := seen의 최솟값
- seen[min_value]를 1 감소
- seen[min_value]가 0이 되면 해당 키를 seen에서 삭제
- j를 0부터 m-1까지 순회:
- seen의 최솟값을 반환
예제 코드
더 나은 이해를 위해 다음 파이썬 구현 예제를 살펴보겠습니다.
def solve(matrix, k):
m, n = len(matrix), len(matrix[0])
for i in range(m):
for j in range(n):
if j:
matrix[i][j] ^= matrix[i][j-1]
seen = {}
count = 0
for i in range(n):
for j in range(m):
if j:
matrix[j][i] ^= matrix[j-1][i]
seen[matrix[j][i]] = seen.get(matrix[j][i], 0) + 1
count += 1
if count > k:
min_value = min(seen)
seen[min_value] -= 1
if not seen[min_value]:
seen.pop(min_value)
return min(seen)
matrix = [[5,2],[1,6]]
k = 1
print(solve(matrix, k))입력
[[5,2],[1,6]], 1
출력
7
복잡도 분석
시간 복잡도는 O(m × n × k)입니다. 각 좌표를 처리할 때마다 count가 k를 초과하는 경우 딕셔너리 전체(최대 k+1개 원소)에서 최솟값을 찾아야 하기 때문입니다. 공간 복잡도는 상위 k개의 값만 저장하므로 O(k)입니다.