배열을 활용한 알고리즘 문제풀이

오늘 푼 문제: 2433. Find The Original Array of Prefix Xor

입출력

• 입력: xor 연산의 결과값인 정수 배열 pref가 주어집니다.
• 출력: n번째까지의 bit-wise xor 연산을 한 숫자에 대해서 pref[x]의 값의 가지게 하는 숫자들의 배열을 반환합니다.

예제 코드

class Solution {
    public int[] findArray(int[] pref) {
        int[] arr = new int[pref.length];
        arr[0] = pref[0];
        int tmp = pref[0];
        for (int x = 1; x < pref.length; x++) {
            arr[x] = tmp ^ pref[x];
            tmp = tmp ^ arr[x];
        }
        return arr;
    }
}

• bit-wise xor 연산이 연속되어 진행되어야 하기 때문에 변수 tmp에 값을 할당합니다.
• xor 연산의 경우 a ^ b = c일 때 a ^ c = b이기 때문에 해당 내용을 활용하였습니다.
• 매 인덱스마다 tmp의 값에 pref[x]의 값을 연산하여 arr[x]의 값을 찾아낸 뒤
• arr[x]에 할당한 후 해당 값을 tmp에 xor 연산해주었습니다.

회고

• 오늘은 xor연산에 대해서 배웠습니다.
• 비트 연산에 대해서 다시 한번 정리할 필요가 있을 것 같습니다.