99클럽 코테 스터디 27일차 TIL + 배열(Subrectangle Queries)

오늘의 과제

리트코드 medium으로 분류된 Find The Original Array of Prefix Xor 입니다.

 

이번 유형도 배열 입니다.

문제

https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/

 

 

먼저 문제 요구사항 요약입니다.

 

prefixXor 배열이 주어질 때 해당 배열을 원래 배열로 복원하여 반환하면 됩니다.

 

이 문제를 풀기 위해서는 동일한 값을 두 번 XOR하면 원래의 값으로 돌아온다는 XOR의 특성을 알아야 합니다.

주어진 prefixXor은 원래 배열의 각 요소까지의 XOR 누적 값을 나타내는데 XOR 연산은 두 비트가 같으면 0, 다르면 1이 되는 연산입니다. 예를 들면 0번째 인덱스는 원래 배열의 첫 번째 요소, 1번째 인덱스는 첫 번째 요소와 두 번째 요소의 XOR 누적 값입니다.

 

이를 풀어서 적어보면 다음과 같이 계산될 수 있습니다.

prefixXor[0] = arr[0]

prefixXor[1] = arr[0] ^ arr[1]

prefixXor[2] = arr[0] ^ arr[1] ^ arr[2]

....

 

prefixXor[i] = arr[i] ^ arr[i - 1]

 

 

코드입니다.

class Solution {
    public int[] findArray(int[] pref) {
        int n = pref.length;
        int[] arr = new int[n];
        
        // 첫 번째 요소는 prefixXor의 첫 번째 요소와 동일합니다.
        arr[0] = pref[0];
        
        // 두 번째 요소부터는 arr[i] = prefixXor[i] ^ prefixXor[i-1] 공식을 사용합니다.
        for (int i = 1; i < n; i++) {
            arr[i] = pref[i] ^ pref[i - 1];
        }
        
        return arr;
    }
}

배운 점

아직 3년차이지만 SI라 그런지는 몰라도 실무에서 비트 연산을 쓸 일이 아예 없기에 조금 헤맸습니다. 학부 수업 내 이론적으로 학습은 했으나 이를 코드로는 안써봐서 조금 헤맸습니다. 앞으로의 문제에도 비트 연산이 나올지는 모르겠으나 더 깊게 파보는 것 보다는 이러한 유형도 있다. 정도로만 참고하고 넘어가려고 합니다.

 

 

 

오늘의 한줄평

때가 쏙 비트