[파이썬] 백준 23295 : 스터디 시간 정하기1 (골드3)

[파이썬] 백준 23295 : 스터디 시간 정하기1 (골드3)

 

23295번: 스터디 시간 정하기 1

---

문제

---

풀이

0. 방향성 생각

시간 초과나서 태그보니까 스위핑이 있길래 찾아봤다.

중요한 점은 시간 입력에서 변화량이 있는 부분만 체크하기. 즉, 시작과 끝 부분만 체크하면 된다.

또 window를 사용하면 자연스럽게 부분합을 사용한다는 점만 인지하면 된다.

이 문제에서는 둘 다 써야함.

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

n,window = map(int,input().split())

time = {}
max_end = 0
for _ in range(n):
    for _ in range(int(input())):
        start,end = map(int,input().split())
        if start in time:
            time[start] += 1
        else:
            time[start] = 1
        if end in time:
            time[end] -= 1
        else:
            time[end] = -1
        max_end = max(max_end,end)

time 딕셔너리를 만들어서 변화량이 있는 부분에만 체크해준다.

start는 가능한 사람이 늘어나므로 +1, end는 가능한 사람이 줄어드므로 -1

또한 입력을 받으면서 효율성을 늘리기 위해 최대 탐색범위 max_end를 정한다. 이 범위를 나가면 변화가 없어서 더 탐색할 필요가 없다.

2. 함수 정의

info,cum = [0],[0]
for i in range(10**5+1):
    if i in time:
        info.append(info[-1]+time[i])
    else:
        info.append(info[-1])
    cum.append(info[-1]+cum[-1])

info에 현재 가능한 인원이 몇명인지 채운다. 변화가 있을 때에만 (i in time) 이전 값에 더해준다.

cum에 누적 인원이 몇명인지 채운다.

 

3. 출력

start,score = 0,0
for i in range(window,max_end+1):
    temp_score = cum[i] - cum[i-window]
    if temp_score > score:
        score = temp_score
        end = i

print(end-window,end)

window 인덱스부터 시작해서 누적합을 구해준다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

n,window = map(int,input().split())

time = {}
max_end = 0
for _ in range(n):
    for _ in range(int(input())):
        start,end = map(int,input().split())
        if start in time:
            time[start] += 1
        else:
            time[start] = 1
        if end in time:
            time[end] -= 1
        else:
            time[end] = -1
        max_end = max(max_end,end)

info,cum = [0],[0]
for i in range(10**5+1):
    if i in time:
        info.append(info[-1]+time[i])
    else:
        info.append(info[-1])
    cum.append(info[-1]+cum[-1])

start,score = 0,0
for i in range(window,max_end+1):
    temp_score = cum[i] - cum[i-window]
    if temp_score > score:
        score = temp_score
        end = i

print(end-window,end)

 

코멘트

스위핑 흡수완료