유니의 편지 쓰기

• 비슷한 문제가 이미 많이 존재하는 문제이다. 강의실 배정, 최소 회의실 개수 등과 같은 문제.
• 강의실 배정, 최소 회의실 개수 과의 차이점은, x월에 입대한 친구와 x월에 전역한 친구가 둘다 존재할때, x월에는 두명이 모두 군대에 있는것으로 처리해줘야 한다는 것. 같은 월에 입대 이벤트와 전역 이벤트가 모두 있을때에는 입대 이벤트가 먼저 처리되도록 정렬 기준을 잡아주면 된다.
• 월 데이터가 문자열로 주어지지만, 포매팅이 잘 되어있어서 굳이 따로 파싱을 하지 않은 채로 그냥 정렬해도 잘 돌아간다
• 시간복잡도는 O(nlogn)
• 이 문제의 경우는, 나올수 있는 월 데이터의 범위가 작은 편이다 (8000*12). 그래서 그냥 정렬 대신에 8000*12 크기에 배열에 바로 카운트를 저장해가면서 처리해도 상관 없다. 카운팅 소트를 하는 것과 비슷한 느낌. 따로 구현은 안했지만, 이 경우에는 O(n+m)로 처리가 가능하고(m은 월 데이터의 범위), 실제 실행 속도도 이쪽이 좀더 빠른것 같다. 이 경우에는 기본적인 파싱은 필요할듯.

"""Solution code for "BOJ 28070. 유니의 편지 쓰기".

- Problem link: https://www.acmicpc.net/problem/28070
- Solution link: http://www.teferi.net/ps/problems/boj/28070
"""

import sys

JOIN = 0
DISCHARGE = 1


def main():
    N = int(sys.stdin.readline())
    events = []
    for _ in range(N):
        join_month, discharge_month = sys.stdin.readline().split()
        events.append((join_month, JOIN))
        events.append((discharge_month, DISCHARGE))

    max_count = count = 0
    answer = None
    for month, type_ in sorted(events):
        count += 1 if type_ == JOIN else -1
        if count > max_count:
            max_count, answer = count, month

    print(answer)


if __name__ == '__main__':
    main()