Practice Coding/Codility

[Lesson 2] - 1. PermCheck

프로그래머 2015. 6. 10. 17:58

문제 : 배열 A가 순열인지 아닌지 판별한다.

접근방법 :  배열의 길이가 4라고 하면 순열이 될 수 있는 조건은 안의 값들이 4, 3, 2, 1이 되어야한다.

                 그렇다면 배열의 길이가 n이라고 하면 1부터 n개의 값이 있는지만 체크하면 된다.

                 하지만 4, 3, 2 ,1은 순열이지만 4, 3, 3, 1 이런 값이 입력된다면 2가 빠져있기 때문에 순열이 아니다.

                 어차피 순열인지 아닌지 확인하기 위해서는 O(n)개 만큼 검색을 해야만 결과값을 받을 수 있다.

                 그래서 생각했던 것이 배열의 개수를 파악할 수 있는 배열을 새로 만들어서 그 값의 카운트를 비교하여 처리하는 방식을 생각했다. 

                 처음에 배열의 길이만큼 초기화를 시켜줘야한다는 비용이 부담되는 문제가 있었지만, 그정도 속도는 큰 문제는 안되었던 것 같다.

                 그리고 반복문 안에 조건을 지정했는데 

                       1) 만약 배열의 값이 1 ~ n 사이의 값이 아니라면 순열이 아니다.

                       2) 카운트 된 배열의 값이 2가 된다면 그것도 순열이 아니다.

사용언어 : Javascript

소스 : 
// you can use console.log for debugging purposes, i.e.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 0.12)
    var cnt = [];
    var len = A.length;
    for (var i=0; i<len;i++) {
        cnt[i] = 0;   
    }
    
    for (var i=0; i<len;i++) {
        if (A[i] == 0 || A[i] > len) 
            return 0;
            
        cnt[A[i]-1]++; 
        
        if(cnt[A[i]-1] > 1) 
            return 0;
    }
    
    return 1;
    
}

득점 :  100점, 다른 접근 방법이 있을 것 같은데.. 


'Practice Coding > Codility' 카테고리의 다른 글

[Lesson 2] - 2. FrogRiverOne  (1) 2015.06.11
[Lesson 1] - 3. TapeEquilibrium  (0) 2015.06.08
[Lesson 1] - 2. PermMissingElem  (0) 2015.06.08
[Lesson 1] - 1. FrogJmp  (0) 2015.06.08
Codility!!  (0) 2015.06.07