문제 : 배열 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
소스 :
득점 : 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 |