반응형
조건 정리
1. 이름이 중복되면 더이상 값을 안받음
2. 겹치는 시간대의 수가 가장 많은 장소를 골라냄
3. 많은 경우 사전순으로 배열
4. 그 중에서 가장 빠른 시간대를 골라냄
풀이
메모리 제한이 512MB인데, 시간대 제한인 50000으로 계산하면 총 제출수 10(각각 다른 장소 일 수 있으므로)*50000*4(int)가 되겠다. 총 2MB이므로 매우 널널하게 잡아 줄 수 있다.
그래서 장소마다 딕셔너리로 50000따리 리스트를 할당했다.
그리고 제출 받을때, 시작점과 끝점까지 반복시키며 시간대를 증가시켜준다. 가장 큰 숫자가 찍힌 부분이 겹치는 부분이다.
그리고 동시에 겹치는 부분이 가장 큰 장소를 maxplace에 저장했다. maxplace의 숫자가 크다면, maxpace를 비워주고, 그것만 추가한다. 반면에 둘이 같다면 maxplace에 해당 값을 추가한다.
출력시에는 사전순으로 정렬해 주고, 가장 작은 값을 골라서 출력한다.
그리고 가장 빠른 시간대를 찾아주고, 이후로 겹치는 부분이 끝나는 시간대를 찾아서 출력해주면된다.
n=int(input())
place=[]
time=dict()
maxplace=[]
name=[]
for _ in range(n):
l=list(map(str, input().split()))
if l[0] not in name:
name.append(l[0])
if time.get(l[1]) is None:
time[l[1]]=[0 for _ in range(50001)]
for x in range(int(l[2]),int(l[3])):
time[l[1]][x]+=1
if not maxplace:
maxplace.append([l[1],1])
else:
placename, cnt=maxplace.pop()
if cnt<max(time[l[1]]):
cnt=max(time[l[1]])
placename=l[1]
while maxplace:
maxplace.pop()
elif cnt==max(time[l[1]]):
maxplace.append([l[1],max(time[l[1]])])
maxplace.append([placename,cnt])
if l[1] not in place:
place.append(l[1])
if len(maxplace)==1:
p,maxx=maxplace.pop()
else:
maxplace.sort(key= lambda x:x[0])
p,maxx=maxplace[0][0],maxplace[0][1]
print(p, end=' ')
for x in range(50001):
if time[p][x]==maxx:
start=x
break
for x in range(start, 50001):
if time[p][x]!=maxx:
end=x
break
print(start,end)
반응형
