[Counting Elements] PermCheck

[Counting Elements] PermCheck

URL : https://codility.com/programmers/lessons/4-counting_elements/perm_check/

N개의 정수로 구성된 배열 A가 주어집니다.

permutation이란 1~N까지 각 원소가 하나씩 포함된 순열을 말합니다.

예를 들어 permutation을 만족하는 배열 A가 아래와 같이 주어집니다.

A[0] = 4     A[1] = 1     A[2] = 3     A[3] = 2

만약 배열 B가 아래와 같이 주어진다면, permutation을 만족하지 않습니다.

B[0] = 4     B[1] = 1     B[2] = 3

2가 없기 때문이죠.

이 문제의 목표는 배열 A가 permutation인지 체크하는데 있습니다.

배열 A가 주어지고, 이 배열이 permutation일 때 1, 그렇지 않을 때 0을 반환하는 함수를 작성해봅시다.

위의 예제에서 A를 입력으로 한 경우 1, B를 입력으로 한 경우 0을 반환해야 합니다.

제약 조건 :

- 배열의 길이 N은 1~100,000범위의 정수입니다.

- 배열 A의 각 원소는 1~1,000,000,000 사이의 정수입니다.

- 시간복잡도는 O(N), 공간복잡도는 O(N) 입니다.

C언어 100% 점수 획득 코드

int solution(int A[], int N) {

int i, temp=0;

for(i=0; i<N; i++) {

temp ^= i+1;

temp ^= A[i];

}

if(temp == 0) return 1;

else return 0;

}

공간복잡도를 요구하는게 메모리를 딱 그만큼 사용하라는 건지 모르겠네요.

N만큼 안쓰고도 풀리니 좋은 코드라고 생각하면 될까요?

저번 포스팅 PermMissingElem과 비슷하게 풀었습니다.

이번에는 빼기 연산이 아니라, XOR(^)연산을 사용해서 풀었습니다.

XOR는 비트연산으로, 같은 수끼리 XOR하게 되면 0, 다른 수끼리 XOR 하면 1을 결과로 반환합니다.

저는 이것을 이용해서 temp라는 integer 변수를 0으로 초기화 하고 거기에 1~N까지 XOR 연산을 해주었습니다.

또 배열 A의 각 원소들을 XOR 연산해주었습니다.

A에는 1~N까지 모든 숫자가 포함되어 있을 것이고,

그것을 1~N까지 XOR연산하게 되면, 연산 특성상 0이 되기 때문에 permutation을 확인할 수 있습니다.

만약 A가 연속된 수가 아니라면, XOR했을 때 0이 아닌 다른 값이 나오겠죠.