[Codility] Lesson 4: Counting Elements - PermCheck (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/

PermCheck coding task - Learn to Code - Codility

- N 개의 정수로 구성된 비어있지 않은 배열 A 제공
- 순열(permutation) : 1에서 N까지의 각 요소를 한 번만 포함
- 배열 A가 순열(permutation)인지 확인
- 배열 A가 순열(permutation)이면 1을, 그렇지 않으면 0을 return
- 가장 효율적인 알고리즘 작성

 

Solution

CASE 1: count 체크 및 예외 처리 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    let count = new Array(N+1).fill(0);
    
    for(let i in A){
        if(A[i] > N){
            return 0;
        }
        if(count[A[i]] > 0){
            return 0;
        }
        count[A[i]]++;
    }
    
    for(let i=1; i>N+1; i++){
        if(count[i] != 1){
            return 0;
        }
    }
    
    return 1;
}

• N : 주어진 배열 A의 길이
• count : 배열 A의 요소 값을 카운트할 새로운 배열. 길이는 N+1. 초기값은 0
• 배열 A의 길이만큼 for문을 돌며 count 배열에 개수 체크
  • A[i]의 값이 N보다 크면 1부터 N까지 중에 한 개 이상의 숫자가 빠질수밖에 없으므로 0을 return
  • count[A[i]]의 값이 1이 0보다 크면 이미 한 번 나온 숫자라는 의미이므로 0을 return
• count 배열의 길이(N+1)만큼 for문을 돌며 count 배열의 요소 값을 확인
  
  • 1부터 N까지이므로 1부터 시작
  • count[i] 값에 1이 아닌 값이 있는 경우, 해당 값이 없다는 의미이므로 0을 return (해당 값이 중복되서 나온 경우는 위의 for문에서 이미 체크했기 때문에 0인 경우만 체크하면 됨)
• 모든 for문이 정상적으로 종료되면 배열 A가 순열이라는 의미이므로 1을 return

 

CASE 1: Result

 

CASE 1: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

순열이 아니게 될 경우를 먼저 생각해 해당 경우에 바로바로 0을 return해서 효율성을 높였음