[분석] Codility - PermCheck - Javascript

Codility 연습문제 > PermCheck > Javascript
주어진 배열이 순열인지 확인하는 문제.

실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.

[문제 및 조건]

N 개의 정수로 구성된 비어있지 않은 배열 A가 주어집니다. 보통 순열은 1 ~ N 까지의 각 요소를 한 번만 포함하는 시퀀스를 말합니다.

1. 정수 배열 A 가 주어진다.
2. 1 ~ N 까지 각 요소가 한 번만 포함된 순열인지 확인하라.
   
   

[분석]

1. N 은 1 ~ 100,000 범위 내의 정수이다.
2. A 의 요소는 1 ~ 1,000,000,000 의 범위 내의 정수이다.
3. 예를들어 [4, 1, 3, 2] 가 주어지면 함수는 1을 반환하고, [4, 1, 3] 이 주어지면 함수는 0을 반환한다.
4. A 가 순열이면 1을 비순열이면 0을 반환하라.
   
   

[풀이]

1. 배열 A를 오름차순으로 정렬한다.
2. 순열은 1씩 증가하는 요소들의 집합이다.
3. 요소의 범위는 양의 정수이고 최소값과 최대값의 차이를 이용해 판단할 수 있다.
4. 결과값뿐만 아니라 성능을 측정하는 문제로, 불필요한 2중 반복문을 피해야 합니다.
   
   

function solution(A) {
  const N = A.length;
  // 오름차순 정렬 및 중복 요소가 없는 배열을 만듭니다.
  const numbers = [...new Set(A)].sort((a, b) => a - b);
  const max = numbers[N - 1];
  
  // numbers 배열의 길이가 처음 A의 길이와 다르거나, 
  // numbers.length 가 최댓값가 같지 않으면 비순열로 판단했습니다.
  if ( numbers.length !== N || numbers.length !== max ) {
    return 0;
  }
  
  return 1; 
}

[마치며]

PermCheck 문제는 for 반복문을 사용하지 않고 순열을 판단할 수 있는지가 중요한 포인트인 것 같습니다. 반복문을 통해 요소 하나하나를 검증할 수도 있겠지만 순열이라는 특성을 어느 정도 이해한다면 쉬운 방법으로 해결이 가능한 문제인 것 같습니다. 또한 시간 복잡도는 O(N) or O(N * log(N))으로 성능 테스트도 문제없이 통과했습니다.