728x90
반응형
문제 바로가기
문제:
모기를 싫어하는 지동이는 어느 날 문득 자신의 방에 모기가 가장 많이 있는 시간대가 언제인지 궁금해졌다. 다행히 지동이 방은 최첨단 시스템이 갖춰져 있어 어떤 모기가 방에 언제 입장했고 언제 퇴장했는지를 기록할 수 있다. 지동이를 도와 모기들의 방 입장, 퇴장 시각이 주어졌을 때 모기들이 가장 많이 있는 시간대와 해당 시간대에 모기가 몇 마리가 있는지 구하는 프로그램을 만들어보자.
입력:
첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE < TX ≤ 2,100,000,000) 모기는 [TE, Tx)동안 존재한다.
출력:
첫째 줄에 지동이 방에 모기가 가장 많이 있는 시간대의 모기 마릿수를 출력한다. 지동이 방에 모기가 가장 많이 있는 시간대의 연속 구간 전체를 [TEm, TXm)이라고 할 때, 둘째 줄에 TEm, TXm을 공백으로 구분하여 출력한다. 단, 여러 가지 방법이 있으면 가장 빠른 시작 시각을 기준으로 출력한다.
풀이:
import collections
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N = int(sys.stdin.readline())
lst = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(N)] # 모기의 입장 시각과 퇴장 시각을 입력 받아 2차원 리스트로 저장
dic = collections.defaultdict(int) # 각 시간대에 대한 누적 모기 수를 저장하기 위한 딕셔너리 생성
for left, right in lst:
dic[left] += 1 # 입장 시각에 대한 모기 수를 1 증가
dic[right] -= 1 # 퇴장 시각에 대한 모기 수를 1 감소
times = sorted(dic.keys()) # 딕셔너리의 키를 정렬하여
cnt = 0 # 모기 마릿수를 저장
res = [0, 0] #시작 시각과 끝 시각
mogi = 0 # 현재 시간대 누적 모기 수
check = False # 모기가 가장 많이 있는 시간대의 시작 시각인지 확인하기 위한 변수
# 즉 뒤에 나올 똑같이 많은 모기 횃수를 저장하기 위함이다.
for time in times:
mogi += dic[time] # 현재 시간대에서 모기 수를 누적
if mogi > cnt: # 누적 모기 수가 최대값보다 큰 경우
cnt = mogi # 최대값을 갱신
res[0] = time # 시작 시각을 갱신
check = True # 시작 시각이 갱신됨을 표시
elif mogi < cnt and check: # 누적 모기 수가 최대값보다 작고, 시작 시각이 갱신된 경우
res[1] = time # 끝 시각을 갱신
check = False # 끝 시각이 갱신됨을 표시
print(cnt) # 모기가 가장 많이 있는 시간대의 모기 마릿수 출력
print(*res) # 모기가 가장 많이 있는 시간대의 시작 시각과 끝 시각을 출력
좀 어려운 문제이다.
아이디어는 쉬운데 구현이 좀 어렵다. 골드 문제여서 시작값과 끝값 사이에 딕셔너리 값에 카운트 하는것을 안했고
첫값과 끝값만 가지고 사용하는것을 생각했다.
반응형
댓글