[알고리즘 수학] 살아있기 좋은 날

세계 과학의 역사라는 책을 준비 중인 편집자가 주요 과학자가 가장 많이 살아 있던 시기를 알아 보려고 한다.

여기서 주요 과학자는 그 책에 출생연도와 사망연도가 모두 기록된 과학자로 정의한다.(그 책에 살아 있는 과학자는 수록되어 있지 않다)

책의 색인을 입력 받아 이 작업을 처리해보자.

만약 A가 사망한 해에 B가 새로 태어났다면 A의 사망시점이 B의 출생 시점보다 앞선다고 가정하자.

문제 출처)길벗출판사- 알고리즘 퍼즐

 

문제풀이)

이 문제는 자료구조의 count배열을 사용하여 해결이 가능하다.

예를 들어 다음과 같이 (태어난 해,사망한해)의 형태로 데이터가 입력 되었다고 가정해 보자.

A(1,9),B(4,7),C(2,10),D(7,11),E(3,12)

태어난 해에는 +1,사망한 해에는 -1로 표기를 해 놓는다.

이렇게 표기해 놓은 다음 앞에서 부터 누적한 배열을 생성한다면 다음과 같은 배열을 만들 수 있다.

이렇게 누적 값을 이용하면 4~8년 사이에 4명의 과학자가 살아 있는 것을 알 수 있다.

 

C++언어로 프로그래밍을 해 보면 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

int main(){
    //freopen("input.txt","r",stdin);
    int n;
    int cnt[3000]={0};
    cin >> n; ///n 명의 과학자 정보를 입력 받는다.
    for(int i=0;i<n;i++){
        int birth,death;
        cin >> birth >> death ; ///태어난 해와 사망한 해를 입력  받는다.
        cnt[birth]++;
        cnt[death]--;
    }
    for(int i=1;i<3000;i++) cnt[i]+=cnt[i-1]; ///cnt 배열을 누적한다.
    
    int ans=0;
    for(int i=1;i<3000;i++) ans=max(ans,cnt[i]); ///cnt 배열에서 가장 큰 값을 찾는다.
    cout << ans << "\n"; ///최대로 살아 있는 과학자 수
    for(int i=1;i<3000;i++){
        if(cnt[i-1]!=ans && cnt[i]==ans){
            cout << i << "~";
        }
        if(cnt[i-1]==ans && cnt[i]!=ans){
            cout << i-1 << "\n";
        }
    }
    return 0;
}