문제 https://leetcode.com/problems/number-of-unique-xor-triplets-ii 풀이 n 길이의 배열 nums가 주어지고, 여기에서 3개의 인덱스 i, j, k를 (i <= j <= k) 뽑아서 XOR 했을 때, 얻을 수 있는 모든 결과의 수를 리턴하는 문제이다. Leetcode 3513 문제와 다른 점은, nums가 순열이 아니다. 따라서, 자연스럽게 모든 경우의 수를 커버하지 못한다. 다만, 인덱스 제약조건이 저번과 같으므로 ‘값 3개를 무작위’로 뽑는다는 점은 같다. 여전히 n이 최대 1500이기 때문에, $O(n^3)$ 으로 풀기에는 무리가 있다. 우선, 값의 중복을 가리지 않고, 인덱스도 가리지 않으므로 배열의 순서가 중요하지 않다. 따라서 배열에 있는 모든 중복을 제거하는 전처리를 한다. ...
문제 https://leetcode.com/problems/number-of-unique-xor-triplets-i 풀이 1에서 n까지의 모든 값이 들어있는 n 크기 배열 nums 배열이 주어지고, 그 배열에서 인덱스 3개 i, j, k (i <= j <= k)를 골라서 XOR 했을 때, 나올 수 있는 모든 값을 리턴하면 되는 문제이다. nums 배열의 크기가 10만이고, 브루트 포스를하면 시간 복잡도가 $O(n^3)$ 이기 때문에 시간 내에 해결할 수 없다. nums가 순열이라는 것과 XOR의 연산 특징을 알면 생각보다 간단한 공식으로 해결할 수 있다. 우선 인덱스 제약조건은 없는 것과 마찬가지인데, 등호를 포함한 대소관계이기 때문에, 인덱스를 중복해서 골라도 된다. ...
기본 소개 비트 마스킹은 비트 연산을 활용해서 집합을 구현하는 방법이다. 각 자리수의 비트는 하나의 원소를 나타내며, 이 원소들이 모여서 집합을 구성하게 된다. 예를 들어, 원소 A, B, C, D를 각각 다음과 같이 표현할 수 있다: let A = 0b0001 // 1 let B = 0b0010 // 2 let C = 0b0100 // 4 let D = 0b1000 // 8 혹은 쉬프트 연산을 활용해서 표현할 수도 있다. 이 방법이 조금 더 직관적이고 단순하다: let A = 1 << 0 let B = 1 << 1 let C = 1 << 2 let D = 1 << 3 이렇게 원소들을 정의하게 되면, 각 원소들이 각각의 자릿수를 점유하고 있기 때문에 겹칠 일이 없다. 따라서 2진수로 쉽게 집합을 표현할 수 있다. ...