[python] Codility Lesson 8-2. EquiLeader

처음 문제를 보고 한동안 O(N^2)방법 밖에 생각이 들지않아 O(N^2)방법으로 먼저 작성해보고,

 

시간 복잡도를 줄일 방법을 생각해 보았다.

 

1. dic_second에서 leader를 먼저 구하자, 그런다음 leader가 없다면 return 0을 해주자.

 

2. for문을 돌면서 dic_first를 채워 주며, 해당 dictionory값을 dic_second에서 -1 씩 지워주자.

 

3. dic_first와 dic_second에서 learder에 해당하는 키값이 각각의 leader가 된다면 answerCnt += 1 해주자.

 

4. 예외 상황으로 leader가 dic_first의 key값으로 있는지 확인해주자.

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    dic_first = dict()
    dic_second = dict()
    answerCnt = 0
    leader = 0
    leaderExist = False
    
    for i in range(len(A)):
        if A[i] in dic_second:
            dic_second[A[i]] += 1
        else:
            dic_second[A[i]] = 1
        if dic_second[A[i]] > len(A)//2:
            leader = A[i]
            leaderExist = True


    for i in range(len(A)-1):
        if A[i] in dic_first:
            dic_first[A[i]] += 1
            dic_second[A[i]] -= 1
        else:
            dic_first[A[i]] = 1
            dic_second[A[i]] -= 1
        if not leader in dic_first:
            continue
        if leaderExist and dic_first[leader] > (i+1) // 2 and dic_second[leader] > (len(A)-(i+1)) // 2:
            answerCnt += 1

    return answerCnt

 

 

 

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    answerCnt = 0
    for i in range(len(A)):
        dic_first = dict()
        dic_second = dict()
        equi_first = -1
        equi_second = -2
        for j in range(i+1):
            if A[j] in dic_first:
                dic_first[A[j]] += 1
            else:
                dic_first[A[j]] = 1
            if dic_first[A[j]] > (i+1) // 2:
                equi_first = A[j]
                break
        for k in range(i+1,len(A)):
            if A[k] in dic_second:
                dic_second[A[k]] += 1
            else:
                dic_second[A[k]] = 1
            if dic_second[A[k]] > (len(A)-(i+1))//2:
                equi_second = A[k]
                break
        if equi_first == equi_second:
            answerCnt += 1
    
    return answerCnt