문제 소개
배열 nums와 정수 k가 주어져 있다고 가정해 보겠습니다. 세그먼트 [left, right](단, left ≤ right)의 XOR이란 해당 범위에 포함된 인덱스의 모든 요소를 순서대로 XOR한 값을 의미합니다.
목표는 크기가 k인 모든 세그먼트의 XOR이 0이 되도록 배열에서 변경해야 하는 요소의 최소 개수를 구하는 것입니다.
예를 들어 입력이 nums = [3,4,5,2,1,7,3,4,7], k = 3이라면 정답은 3입니다. 인덱스 2, 3, 4의 요소를 수정해 배열을 [3,4,7,3,4,7,3,4,7] 형태로 만들면, 크기 3인 모든 세그먼트의 XOR이 0이 되기 때문입니다.
풀이 접근 방법
이 문제는 동적 계획법(DP)과 XOR 비트 연산을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 인덱스를 k로 나눈 나머지(i mod k)가 같은 위치들을 하나의 그룹으로 묶습니다. 크기 k인 모든 세그먼트에는 각 그룹의 요소가 정확히 하나씩 포함됩니다.
- 각 그룹별로 어떤 값이 몇 번 등장하는지 빈도를 미리 계산합니다.
- DP 테이블 dp[x]는 "지금까지 처리한 그룹에서 선택한 값들의 XOR이 x일 때, 변경하지 않고 유지할 수 있는 요소의 최대 개수"를 저장합니다.
- 특정 그룹 전체를 변경하는 경우에는 dp의 최댓값(maxprev)을 그대로 이어받고, 기존 값을 유지하는 경우에는 빈도(cnt)만큼 이득을 얻습니다.
- 최종적으로 dp[0]이 유지 가능한 최대 요소 수이므로, 전체 길이에서 이 값을 빼면 최소 변경 횟수가 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다 −
LIMIT := 1024 (요소 값의 상한)
temp := LIMIT × k 크기의 2차원 배열을 생성하고 0으로 초기화
nums의 각 인덱스 i와 값 x에 대해 다음을 수행
temp[i mod k][x] := temp[i mod k][x] + 1
dp := LIMIT 크기의 배열을 생성하고 -2000으로 초기화 (도달 불가능한 상태 표시)
dp[0] := 0
temp의 각 행(row)에 대해 다음을 수행
maxprev := dp의 최댓값 (해당 그룹 전체를 변경하는 경우)
new_dp := LIMIT 크기의 배열을 생성하고 maxprev로 초기화
행의 각 인덱스 i와 빈도 cnt에 대해 다음을 수행
cnt > 0인 경우, dp의 각 인덱스 j와 값 prev에 대해 다음을 수행
new_dp[i XOR j] := new_dp[i XOR j]와 prev + cnt 중 더 큰 값
dp := new_dp
len(nums) − dp[0]을 반환
예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(nums, k): LIMIT = 2**10 temp = [[0 for _ in range(LIMIT)] for _ in range(k)] for i, x in enumerate(nums): temp[i % k][x] += 1 dp = [-2000 for _ in range(LIMIT)] dp[0] = 0 for row in temp: maxprev = max(dp) new_dp = [maxprev for _ in range(LIMIT)] for i, cnt in enumerate(row): if cnt > 0: for j, prev in enumerate(dp): new_dp[i ^ j] = max(new_dp[i ^ j], prev + cnt) dp = new_dp return len(nums) - dp[0] nums = [3,4,5,2,1,7,3,4,7] k = 3 print(solve(nums, k))
입력
[3,4,5,2,1,7,3,4,7], 3
출력
3
코드 설명 및 복잡도 분석
먼저 각 위치를 k로 나눈 나머지별로 값의 등장 빈도를 temp 배열에 누적합니다. 이후 각 그룹을 순회하면서 두 가지 선택지를 비교합니다. 첫째, 해당 그룹의 모든 요소를 변경하는 경우(비용 없이 maxprev 유지), 둘째, 이미 존재하는 값 하나를 유지하는 경우(prev + cnt만큼 이득). 두 경우를 XOR 상태 전이에 반영하며 DP를 갱신합니다.
시간 복잡도는 빈도 계산에 O(n), DP 전이에 최악의 경우 O(k × LIMIT²)가 소요되며, 공간 복잡도는 O(k × LIMIT)입니다. n이 크고 k가 작은 입력에서도 충분히 실용적인 성능을 보입니다.