[C언어 풀이] Codility - Lessons 4, (Counting Elements) PermCheck

 

 

 

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

문제

 

 

 

설명

 

배열의 순열을 찾는 문제 입니다.

Codility - Lessons 3, (Time Complexity) PermMissingElem <<-- 이 문제와 비슷합니다.

배열 요소는 1~1,000,000 까지 범위고 

배열의 최대길이 N은 1~100,000입니다.

 

배열 요소는 정렬되어 있지 않고 배열의 요소들이 순열이면 return 1, 순열이 아니면 return 0 을 하는 코드를 만들면 됩니다.

 

단, 순열은 무조건 1부터 시작한다는 조건이 있습니다.

 

 

 

 

결과

 

 

https://app.codility.com/demo/results/trainingU4E72T-W7Y/

 

 

 

 

 

소스코드

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int i, quo, ren, sum = 0;
     
    quo = N/4;
    ren = N%4;
     
    for(i = 0; i < N; i++)
        sum ^= A[i];
         
     
    if(ren == 0 && sum == quo * 4)
        return 1;
    else if(ren == 1 && sum == 1)
        return 1;
    else if(ren == 2 && sum == ((quo + 1) * 4) - 1 )
        return 1;
    else if(ren == 3 && sum == 0)
        return 1;
    else
        return 0;
}​

 

처음엔 "아 쉽겠다.!!" 라고 생각해서  Codility - Lessons 3, (Time Complexity) PermMissingElem 과 비슷하게 풀었습니다.

 

그런데 이런식으로 푸니깐 [1, 4, 1] 인 상황에선 0을 반환해야 하는데 1을 반환하게 되더라고요......

 

그래서 다른 방법 없을까 생각하다가 "XOR을 사용하면 어떤식으로 될까?"를 생각하게 됐고 XOR을 사용했을 때

 

순열에서 패턴을 찾아 적용시켰습니다.

 

패턴은 이렇습니다.

0 ~ 14 까지의 순열을 XOR 시킨 값 입니다.

 

0, 0, 1, 3,  0, 4, 1, 7,   0, 8, 1, 11,  0, 12, 1, 15

 

첫번째와 세번째는 0과 1로 고정이고

2번째는 4의 배수.

4번째는 3+4의 배수.

 

이를 활용하여 작성된 코드가 위 코드 입니다.

 

 

 

처음 생각해서 75점 맞은 코드는 아래에 기재하겠습니다.

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int i, quo, ren, sum = 0;
     
    sum = 1 + N;
    quo = N/2;
     
     
    if(N%2 == 0)
        sum = sum * quo;
    else
        sum = (sum * quo) + quo + 1;
     
    for(i = 0; i < N; i++)
        sum -= A[i];
         
     
    if(sum == 0)
        return 1;
    else
        return 0;
     
}

 

https://app.codility.com/demo/results/training9VZVCC-YSF/

Test results - Codility