파이썬으로 인구가 가장 많았던 해 찾기: 알고리즘과 구현 예제

문제 개요

두 개의 열(출생 연도, 사망 연도)로 구성된 표가 있다고 가정해 보겠습니다. 각 행은 i번째 사람의 출생 연도와 사망 연도를 나타냅니다.

여기서 특정 연도 y의 인구란, y년 동안 생존해 있던 사람의 수를 의미합니다. i번째 사람은 y가 [birth_i, death_i - 1] 범위(양 끝 포함)에 속할 때 y년의 인구에 포함됩니다. 즉, 사망한 해 본인은 인구 집계에서 제외됩니다.

우리가 구해야 할 것은 인구가 최대가 되는 해 중 가장 이른 연도입니다.

입력 예시

이 경우 출력은 1960입니다. 1960년부터 1969년까지 두 번째(1960년생)와 세 번째(1940년생) 사람이 모두 생존해 있어 인구가 2명으로 최대이며, 그중 가장 이른 해가 1960년이기 때문입니다.

풀이 접근 방법

각 연도별로 생존 인원 수를 누적하여 계산하면 문제를 해결할 수 있습니다. 절차는 다음과 같습니다.

• d : 키가 존재하지 않으면 기본값 0을 반환하는 맵(defaultdict)을 생성합니다.

• res : 결과를 저장할 리스트를 [2051, 0]으로 초기화합니다. (2051은 충분히 큰 임의의 연도 값)

• 행렬의 각 (출생 연도 YOB, 사망 연도 YOD) 쌍에 대해 반복합니다.

  • YOB부터 YOD-1까지의 각 연도에 대해:

    • d[year] 값을 1 증가시킵니다.

    • d[year] >= res[1]이라면:

      • d[year] > res[1]인 경우(인구가 더 많아진 경우): res를 [year, d[year]]로 갱신합니다.

      • 그렇지 않은 경우(인구가 같은 경우): 더 이른 연도를 유지하기 위해 res를 [min(year, res[0]), res[1]]로 갱신합니다.

• 최종적으로 res[0](최대 인구를 기록한 가장 이른 연도)을 반환합니다.

파이썬 구현 코드

다음 구현을 통해 더 잘 이해해 보겠습니다.

예제 코드

from collections import defaultdict
def solve(matrix):
   d = defaultdict(int)
   res = [2051, 0]
   for YOB, YOD in matrix:
      for year in range(YOB, YOD):
         d[year] += 1
         if d[year] >= res[1]:
            if d[year] > res[1]:
               res = [year, d[year]]
            else:
               res = [min(year, res[0]), res[1]]
   return res[0]
matrix = [[1970,2010],[1960,2020],[1940,1970]]
print(solve(matrix))

입력

[[1970,2010],[1960,2020],[1940,1970]]

출력

1960

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N × L)입니다. 여기서 N은 사람의 수, L은 평균 수명(연 단위)입니다. 각 사람의 생존 기간 동안 매년 카운트를 증가시키기 때문입니다. 공간 복잡도 역시 O(L)로, 연도별 인구를 저장하는 딕셔너리 크기에 비례합니다.

만약 입력 데이터의 연도 범위가 매우 넓다면, 각 연도를 일일이 순회하는 대신 스윕 라인(sweep line) 기법이나 차분 배열(diff array)을 활용하면 더 효율적으로 최적화할 수 있습니다.