Codility Lesson 4 - PermCheck

문제 설명

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다.

순열은 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가 주어졌을 때 배열 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] 범위 내의 정수입니다.

문제 접근

빈 객체에 1부터 A.length 까지에 숫자를 저장하고 배열 A를 순회하면서 빈 객체를 존재하는 A[index] 값을 삭제한다.

마지막에 해당 객체의 숫자가 모두 없으면 순열(연속된 수)이고 그렇지 않으면 순열이 아니라는 것이다.

1. 빈 객체에 1 부터 A.length 까지에 숫자를 추가한다.
2. 배열 A 를 순회하면 A[index] 값이 객체 존재하면 객체에 해당 숫자를 삭제한다.
3. 모든 순회를 다 진행하고 객체에 숫자가 존재하지 않으면 0 반환 그렇지 않으면 1 반환

function solution(A) {
  const info = new Set()

  for (let i = 1; i <= A.length; i++) {
    info.add(i)
  }

  for (let i = 0; i < A.length; i++) {
    if (info.has(A[i])) {
      info.delete(A[i])
    }
  }

  return info.size === 0 ? 1 : 0
}