PermCheck

/Codility

문제 해석

요약

1부터 N까지 각 요소를 단 한 번씩만 포함하고 있는 순열(Permutation)인지 판단하고 맞으면 1, 아니면 2를 리턴

전문

🇰🇷 번역

N개의 정수로 이루어진 비어있지 않은 배열 A가 주어진다.

순열(Permutation)은 1부터 N까지 각요소를 단 한번만 포함하고 있는 시퀀스이다.

배열 A가 다음과 같다면:

A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
이것은 순열이고, 반면에 배열 A가 다음과 같다면:

A[0] = 4
A[1] = 1
A[2] = 3
이것은 순열이 아니다. 왜냐하면 2의 값이 없기 때문이다.

A가 순열인지 체크하는 것이 목적이다.

함수를 작성하시오:
function solution(A);

배열 A가 주어지면, 순열이면 1을, 아니라면 0을 반환하여라.

배열 A가 다음과 같다면:

A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2
함수는 1을 반환해야 한다.

주어진 배열 A가 다음과 같다면:
A[0] = 4
A[1] = 1
A[2] = 3

함수는 0을 반환해야한다.

다음과 같은 가정에 따라 효율적인 알고리즘을 작성하시오:

  • 정수 N는 [1..100,000]범위 안의 정수이다;
  • 배열 A의 각 요소는 [1..1,000,000,000]범위 안의 정수이다.

🇺🇸 원문

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].

🤔 문제 해결 방법 구상

1부터 N까지 중복없는 순열(Permutation)인지 파악하고, 수열이면 1, 아니면 0을 리턴하는 것이다.

결국 비어있는 정수를 찾던 문제인 MissingInteger와 비슷하다.

다만, 다른 조건이 있으니 주의해야한다. 모두 양수이며, 숫자가 중복되면 순열이 아니기 때문에 0을 리턴 해야 한다는 점이다.

  1. 주어진 배열 A를 Set로 새로 만든다.
  2. 배열 A의 길이와, setA의 사이즈 비교

    • 값이 다르다면, 중복되는 사항이 있는 것이므로 0 리턴.
  3. loop을 돌며 있는지 확인.

    • 1부터 Set의 최대 크기만큼 loop을 돌면 된다.
    • 값이 있는지 확인하고, 없다면 바로 0 리턴.
  4. 끝날때 까지 값이 안나온다면, 1 리턴.

코드 구현

function solution(A) {
  const setA = new Set(A);
  const max = setA.size;
  if (A.length !== max) return 0;

  for (let i = 1; i <= max; i++) {
    if (!setA.has(i)) return 0;
  }

  return 1;
};

결과 분석

Task Score: 100%
Correctness: 100%
Performance: 100%

시간 복잡도는 O(N) or O(N * log(N)). 공간 복잡도는 O(n)으로 예상한다.

오 모두 통과~ sort메소드를 사용하니 확실히 편리하긴 하다.

마무리

참고로 둘 다 테스트도 통과하고, 시간 복잡도도 같지만 시간에서 차이가 났다. codility에서는 테스트 통과 시간이 얼마나 걸리는지 알려주는데, 모든 테스트에서 Set를 사용한 코드가 더 빨랐다. 즉, 배열의 값을 하나씩 비교하는 것 보다, 객체로 접근하는 것이 더 빠르다는 것을 확인한 것이다.

Reference & Learn More

MDN Set
MDN Set.prototype.size
MDN Set.prototype.has()
[MDN Array.prototype.sort()][mdnsort]

Tags
Comments