16.10 살아있는 사람

문제 

사람의 태어난 연도와 사망한 연도가 리스트로 주어졌을때, 가장 많은 사람이 동시에 살았던 연도를 찾는 메서드를 작성하라. 모든사람이 1900년도에서 2000년도 사이에서 태어났다고 가정해도 좋다. 또한 해당 연도의 일부만 살았더라도 해당 년도에 살아있었다고 봐야한다. 예르르들어 어떤 사람이 1908년에 태어나서 1909년에 사망했다면 이 사람은 1908년과 1909년 모두에 삶을 살았던 사람이된다.

 

해결법

1. 무식한 방법

각 년도를 순회하면서 각 년도에 살아있는 사람들을 카운트한다. 

R이 가능한 연도의 범위이고 P가 사람의 수라고 했을때 시간 복잡도는 O(RP)가 된다. 

 

2. 무식하지만 조금 나은 방법

해마다 태어난 인구수를 기록하는 배열을 만들고, 사람을 순회하면서 배열에 기록한다. 

(배열을 잡을때 1900-2000 = 100개로 잡으면안되고 101개로 잡아야한다. 1900과 2000이 포함되기 때문)

R이 가능한 연도의 범위이고 P가 사람의 수라고 하고 그사람이 살았던 구간을 Y라고 하면 

O(PY + R) 이 된다. 하지만, Y=R이면 1번방법과 크게 달라지지 않는다.

 

3. 더 최적화 

어쩌피 사람들의 정보 (태어난시간, 사망한시간)을 그대로 보존할 필요가 없다는 사실을 안다면 정렬을 해도좋다.

태어난 시간끼리 정렬, 사망한 시간끼리 정렬을 한 다음에 하나씩 읽어들어가면서 사람이 태어났을때 +1 죽었을때는 -1을 하면서 최대 시간을 확인하면된다.

def maxAliveYear(births, deaths, min, max):
    births.sort()
    deaths.sort()

    maxAlive = 0
    maxYear = 0
    curAlive = 0
    
    birthIndex = 0
    deathIndex = 0
    len_peoples = len(births)
    while deathsIndex != len_peoples:
        if birth[birthIndex] <= deaths[deathIndex] :
            curAlive +=1
            if maxAlive < curAlive :
                maxAlive = curAlive
                maxYear = births[birthIndex]
            birthIndex +=1
        else :
            curAlive -=1
            deathIndex +=1

    return maxYear

이코드를 짤때에 주의해야할 점은 바로 birth[birthIndex] <= deaths[deathIndex] 이다.

<= 인지 < 인지를 결정할때 태어난 년도에 사망한 사람이 있는 경우를 어떻게 처리할지에 대해 생각하면 답이 나온다.

누군가가 해당 년도에 태어났고 누군가는 사망했다면 먼저 태어난것을 먼저 체크하고 그다음에 사망을 체크해주어야한다. 

그러려면 같은 경우에도 살아있는 사람 +1을 먼저 해야할 것이다.

이경우의 Time complexity 는 사람들의 명수가 P일때 O(PlogP)일 것이다. sort가 있기 때문에

 

4. 더 최적화!

PlogP보다 더 빨라지려면 정렬을 하지 말아야한다. 정렬을 안하면서도 최대 명수를 알기 위해서는 각 년도에 몇명이 태어났고 죽었는지를 미리 체크해두면 알 수 있을 것이다.

def getPopulation(populationYears, births, deaths, min):
    for birth in births:
        populationYears[birth-min] +=1
    for death in deaths:
        populationYears[death-min+1] -=1



def maxAlive(births, deaths, min, max):
    populationYears = [0]*(max-min+1)
    getPopulation(populationYears, births, deaths , min)
    
    maxAlive = 0
    maxYear  = 0
    curAlive = 0
    for i, p in enumerate(populationYears):
        curAlive +=p
        if curAlive > maxAlive:
            maxAlive = curAlive
            maxYear = min+i

    return maxYear

이 경우에 조심해야할 부분은 사람이 태어난 년도에 인구+1을 하는 것은 맞지만 사망한 년도에 -1을 하게되면 해당년도에 누군가가 태어나고 누군가가 사망한경우는 상쇄되어 0으로 저장되어진다. 그러면 태어난 것을 카운트 할 수 없기 때문에 이런경우에는 사망년도 다음 년도에 -1을 하게 되면 간단하게 해결이 가능하다.