[프로그래머스] 순열 검사

문제 설명

길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다.
1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.

제한사항

• 배열의 길이는 10만 이하입니다.
• 배열의 원소는 0 이상 10만 이하인 정수입니다.

---

입출력 예arrresult

[4, 1, 3, 2]	true
[4, 1, 3]	false

입출력 예 설명

입출력 예 #1
입력이 [4, 1, 3, 2]가 주어진 경우, 배열의 길이가 4이므로 배열에는 1부터 4까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3, 2]에는 1부터 4까지의 숫자가 모두 들어 있으므로 true를 반환하면 됩니다.

입출력 예 #2
[4, 1, 3]이 주어진 경우, 배열의 길이가 3이므로 배열에는 1부터 3까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3]에는 2가 없고 4가 있으므로 false를 반환하면 됩니다.

 

풀이:

HashMap이나 int array를 사용 가능하나 이럴 경우 공간복잡도가 O(N)이 되버린다.

그래서 O(1)으로 풀는 방법을 생각해봤다.

binary operator 인 ^ (xor) 사용하면 O(1)의 공간복잡도로 해결 가능.

 

1부터 arr크기까지와 arr내부의 있는 모든것을 xor로 통과 시키면 0이 나와야 true 아니면 false.

 

class Solution {
    public boolean solution(int[] arr) {
        boolean answer = true;

        int n=0;
        for(int i=0; i<arr.length; i++){
            n ^= (arr[i] ^ (i+1));
        }
        answer = n == 0 ? true : false;
        return answer;
    }
}