Codility Lesson 8 EquiLeader

http://app.codility.com/programmers/lessons/8-leader/equi_leader/

EquiLeader coding task - Learn to Code - Codility

해당 문제를 Swift로 풀이한 것을 공유하겠습니다.

문제 내용 정리

A non-empty array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

비어있지 않은 N개의 정수를 지닌 배열 A가 존재합니다.

Leader란 배열 데이터 안에서 절반이상 노출되는 데이터를 지칭합니다.

Equi Leader란, 최소 1개 이상의 원소를 포함하도록 배열을 2등분 하는 인덱스 S [0 <= S < N-1]를 기준으로 A[0], A[1], ..., A[S] 그룹의 Leader와 A[S + 1], A[S + 2], ..., A[N − 1] 그룹의 Leader가 동일한 값을 지닐 때를 지칭합니다.

 

[4,3,4,4,4,2] 를 예시로 들면

[4][3,4,4,4,2] / [4,3,4][4,4,2] 해당 2가지가 "4"라는 EquiLeader가 존재합니다.

 

해당 문제는 A라는 배열이 주워졌을 때, EquiLeader가 몇 개 존재하는지 파악하는 것 입니다.

문제 해결 포인트

1. 부분 배열의 Leader가 되려면 전체 배열의 Leader여야 합니다.
2. 전체 배열의 Leader를 찾은 후 인덱스를 순회하며 Leader 갯수 누적 합을 구하고, 편리하게 EquiLeader를 찾습니다.
   • B : 배열의 인덱스 위치 별 갯수의 누적합 => Example A 배열의 B : [ "0" : 1 , "1" : 1, "2" : 2, "3" : 3 ..... ]

코드 공유

문제해결 포인트 1 : findLeader 함수 참고

문제해결 포인트 2 : solution 함수 내부 for 문 참고

public func solution(_ A : inout [Int]) -> Int {
    var answer = 0
    
    if let leader = findLeader(A) {
        for i in (0..<A.count) {
            // i 인덱스까지의 Leader 갯수
            guard let firstGroupLeaderCount = leader[i] else { return 0 }
            guard let totalLeaderCount = leader[A.count-1] else { return 0 }
            
            // i 이후에서 끝까지 Leader 갯수
            let secondGroupLeaderCount = totalLeaderCount - firstGroupLeaderCount
            
            // firstGroupLeaderCount, secondGroupLeaderCount가 각각의 그룹에서 절반초과하게 차지하는지 확인합니다. (짝수,홀수 유념)
            let makeEvenFirstGroupHalfCount = (i+1) % 2 == 1 ? (i+2)/2 : (i+3)/2
            let makeEvenSecondGroupHalfCount = (A.count-1-i) % 2 == 1 ? (A.count-i)/2 : (A.count+1-i)/2
            if (firstGroupLeaderCount >= makeEvenFirstGroupHalfCount && secondGroupLeaderCount >= makeEvenSecondGroupHalfCount) {
                // 둘 다 절반을 초과한다면 답의 개수를 증가시킵니다.
                answer+=1
            }
        }
    } else {
        return 0
    }
    
    return answer
}

// 배열의 Leader를 찾고 인덱스 별 Leader 갯수의 누적합 Dictionary를 반환합니다.
public func findLeader(_ array : [Int]) -> [Int: Int]? {
    var stack: [Int] = .init()
    
    // 스택을 이용하면, 배열에 제일 많이 등장하는 요소를 쉽게 찾아낼 수 있습니다.
    // PDF 최하단 참고 https://codility.com/media/train/6-Leader.pdf
    array.forEach {
        if !stack.isEmpty {
            if let last = stack.popLast() {
                if last == $0 {
                    stack.append(last)
                    stack.append($0)
                }
            }
        } else {
            stack.append($0)
        }
    }
    
    // 만약, stack이 비어있다면, nil을 반환합니다.
    guard let last = stack.last else { return nil }
    
    // 제일 많이 등장하는 요소를 찾았으니, 이제 Leader 인지 판단하기 위해 누적합을 구합니다.
    // 이때 함께, 인덱스 별 누적합 Dictionary를 만듭니다.
    var dict:[Int:Int] = [Int:Int]()
    var count = 0
    
    for i in (0..<array.count) {
        if last == array[i] {
            count += 1
        }
        dict[i] = count
    }
    
    // 총 합(count)이 Leader 조건 (절반 초과 차지)이 안된다면, nil을 반환하고 존재 시 인덱스 별 누적합 Dictionary를 반환합니다.
    return count > array.count/2 ? dict : nil
}