[알고리즘/자바스크립트] Codility, PermCheck 문제 풀이

Codility, PermCheck

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

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

is a permutation, but array A such that:

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

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

function solution(A);

that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

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

the function should return 1.

Given array A such that:

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

the function should return 0.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [1..1,000,000,000].

 

---

 

오랜만에 간단한 알고리즘 문제를 풀어보았다. 쉬운 문제인데다가 간만에 푸니까 재미있다.

문제는 주어진 배열이 Permutation(순열)인지 체크하는 문제인데, 아주 간단하다.

 

Permutation이란, 1부터 N까지의 중복 없는 수열이다.

 

예를 들어서 배열이 [4, 1, 3, 2]라면 1부터 4까지의 중복 없는 수열이므로 Permutation이라고 할 수 있다.

그러나 배열이 [4, 1, 3]이라면 중간에 2가 빠졌으므로 Permutation이 아니다.

 

문제는 A 배열을 인자로 받은 후 Permutation인 경우 1을 리턴하고 Permutation이 아닌 경우 0을 리턴하는 문제이다.

 

N은 1부터 100,000까지의 숫자이며, A 배열의 숫자의 범위는 1부터 1,000,000,000이다.

 

 

function solution(A) {
  A.sort((l, r) => l - r);
  
  if (A[0] !== 1) {
    return 0;
  }
  
  for (let i = 0; i < A.length - 1; i++) {
    if (A[i + 1] - A[i] !== 1) {
      return 0;
    }
  }
    
  return 1;
}

 

내가 푼 방법은 위와 같다.

 

1. A 배열을 오름차순으로 정렬한다.
2. A 배열의 첫 번째 숫자가 1이 아니라면 Permutation 조건에 해당하지 않으므로 0을 리턴한다.
3. 0부터 A.length - 1 까지 순회를 하면서 A[i + 1]과 A[i]의 차가 1이 아닌 경우 0을 리턴한다.
4. 위 조건에 해당하지 않는 경우 Permutation이므로 1을 리턴한다.

즉, 배열의 숫자를 정렬하게 되면 중복이 없고 1부터 시작하는 수열이라면 각 숫자의 차가 1이라면 Permutation이고,

그렇지 않은 경우에는 Permutation이 아니게 된다.