[Codility] 4. PermCheck

[Codility] 4. PermCheck


문제 링크

PermCheck

문제 요약

주어진 배열 A가 순열(permutation)인지 확인.
순열이란 N개의 정수로 구성된 배열 A에서 1에서 N까지 단 한번만 배열 A에 존재하는 경우 A를 순열이라 부른다.
순열이면 1, 아니면 0을 반환!

요구사항

N is an integer within the range [1..100,000]
each element of array A is an integer within the range [1..1,000,000,000]

코드

순열의 조건은 1) 중복이 없고 2) 1~N까지 연속된 수 이다.
우선 주어진 A 배열의 요소를 더해서 비교하면 1~N까지 이루어진 순열의 조건 중 한 가지를 만족시킬 수 있다.
하지만 이것만으론 [1,4,1] 배열과 같이 합이 6이지만, 중복된 수 1은 걸러낼 수 없다.
여기서 Set(hashmap)을 사용한다.
Set에 원소를 넣기 전, A 배열을 순회하여 값이 있는지 판단한다.
값이 없다면 insert를 해주고, 이미 존재한다면 return 시킨다.

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var expectedSum = Int()
    var checkedSet = Set<Int>()
    var sum = Int()
    let Count = A.count

    expectedSum = (Count * (Count+1)) / 2 //모든 원소가 있는지 확인용
    for i in 0..<Count { 
        if(checkedSet.contains(A[i])) {
            return 0
        } else {
            checkedSet.insert(A[i])
        }
        sum += A[i]
    }

    return (sum == expectedSum) ? 1 : 0
}

냠냠

좋은 웹페이지 즐겨찾기