문제 개요
정수 배열이 주어집니다(배열의 크기는 4의 배수). 우리는 이 배열에 배타적 논리합(XOR) 연산을 수행하여, 원본 배열의 각 4개 요소 그룹이 새로운 배열의 해당 그룹과 대응되도록 만들어야 합니다.
계산 조건은 다음과 같습니다.
만약 arr[1~4] = {a1, a2, a3, a4}라면,
q[1~4] = {a1⊕a2⊕a3, a1⊕a2⊕a4, a1⊕a3⊕a4, a2⊕a3⊕a4}
즉, 각 그룹에서 세 개의 요소씩 선택해 XOR한 값들을 순서대로 나열한 것이 결과 배열이 됩니다.
입력 및 출력 예제
입력: int[] input = { 5, 2, 3, 4 };
출력: XOR 연산 후 결과 → 4 3 2 5
설명: XOR(Exclusive-OR) 게이트는 두 입력 단자의 논리 레벨이 서로 '다를' 때만 출력이 'HIGH(1)'가 됩니다. 두 입력 A와 B가 모두 논리 레벨 '1' 또는 모두 '0'이라면 출력은 '0'이 되며, 이 때문에 XOR 게이트는 '홀수 패리티 게이트'라고도 불립니다. 다시 말해, 입력들 중 1의 개수가 홀수일 때 출력이 '1'이 됩니다.
- a1 ⊕ a2 ⊕ a3 = 5 ⊕ 2 ⊕ 3 = 4
- a1 ⊕ a2 ⊕ a4 = 5 ⊕ 2 ⊕ 4 = 3
- a1 ⊕ a3 ⊕ a4 = 5 ⊕ 3 ⊕ 4 = 2
- a2 ⊕ a3 ⊕ a4 = 2 ⊕ 3 ⊕ 4 = 5
입력: int[] input = { 7, 6, 4, 4, 3, 8, 9, 5 };
출력: XOR 연산 후 결과 → 5 5 7 6 2 14 15 4
설명: 이 방식은 크기가 4의 배수인 입력 배열에만 동작합니다. 크기가 4의 배수가 아닌 배열의 경우, 남는 자리의 홀수 위치에는 0이 표시됩니다.
알고리즘 접근 방식
아래 프로그램에서 사용된 핵심 아이디어는 다음과 같습니다.
XOR의 기본 성질을 활용합니다: a ⊕ a = 0, a ⊕ 0 = a. 따라서 (a ⊕ b ⊕ c) ⊕ (b ⊕ c ⊕ d) = a ⊕ d 가 성립합니다. 왜냐하면 (b ⊕ c) ⊕ (b ⊕ c) = 0이기 때문입니다.
계산을 위해 배열을 4개 요소씩의 그룹으로 나누고, 각 그룹에 대해 XOR의 성질을 적용해 결과를 구합니다.
먼저 (a ⊕ d) 값을 구한 뒤, 이를 이용해 b와 c를 계산할 수 있습니다.
(a ⊕ b ⊕ d) ⊕ (a ⊕ d) = b
(a ⊕ c ⊕ d) ⊕ (a ⊕ d) = c구해진 b와 c를 이용하면 a와 d도 다음과 같이 얻을 수 있습니다.
(a ⊕ b ⊕ c) ⊕ b ⊕ c = a
(b ⊕ c ⊕ d) ⊕ b ⊕ c = d이 과정을 모든 그룹에 대해 반복 수행합니다.
포인터 i와 j를 사용한 루프를 배열 길이를 4로 나눈 횟수만큼 돌리며, 임시 변수(ans)와 정답을 저장할 유틸리티 배열(arr)을 준비합니다.
for 루프 내부에서 다음과 같은 XOR 연산이 수행됩니다.
ans = input[i] ⊕ input[i+3]
arr[i+1] (b 계산) = input[i+1] ⊕ ans
arr[i+2] (c 계산) = input[i+2] ⊕ ans
arr[i] (a 계산) = input[i] ⊕ ((arr[i+1]) ^ (arr[i+2]))
arr[i+3] (d 계산) = input[i+3] ⊕ ((arr[i+1]) ^ (arr[i+2]))한 그룹의 처리가 끝나면 포인터를 4만큼 이동시켜 다음 네 개 요소를 처리합니다.
마지막으로 전체 배열을 출력하고 결과를 반환합니다.
예제 코드
import java.util.Arrays;
import java.util.List;
public class Tutorials{
static int ans = 0;
public static void main(String args[]){
int[] input = {7, 1, 2, 3};
int[] arr = new int[input.length];
for (int i = 0, j = 0; j < input.length / 4; j++){
ans = input[i] ^ input[i + 3];
arr[i + 1] = input[i + 1] ^ ans;
arr[i + 2] = input[i + 2] ^ ans;
arr[i] = input[i] ^ ((arr[i + 1]) ^ (arr[i + 2]));
arr[i + 3] = input[i + 3] ^ (arr[i + 1] ^ arr[i + 2]);
i += 4;
}
System.out.println("Different XORs of elements in groups of size 4 is: ");
for (int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Different XORs of elements in groups of size 4 is : 4 5 6 0