[Python] 백준 14572번 : 스터디 그룹

https://www.acmicpc.net/problem/14572

14572번: 스터디 그룹

---

💡 문제 풀이

투 포인터 알고리즘 문제이다.

 

투 포인터 알고리즘 중 누적합과 비슷한 알고리즘을 한 단계 더 올려서 해결하면 되는 문제이다.

E를 계산하는 식을 보면 다음과 같다.

E = (아는 모든 알고리즘(anyknows) - 모두 아는 알고리즘(allknows)) × 그룹원 수 

결정적으로 값을 크게 만드는 것은 그룹원의 수이기 때문에 D를 벗어나지 않는 선에서 가장 그룹원이 많을 때 원하는 값이 있을 확률이 높다.

따라서 D를 벗어나지 않는 범위까지 투 포인터를 옮기면서 계속 값을 계산해 비교해야 한다.

✔️ 느낀 점

처음에 생각한 방법은 다음과 같다.

투 포인터를 구현할 때 그룹원들의 집합과 그룹원들이 알고 있는 알고리즘의 집합을 만들어 값을 수정하면서 계산하고,

알고리즘을 알고 있는 학생들의 리스트와 집합을 비교하면서 진행했다.

그 결과 메모리 초과도 발생하고 시간 초과도 발생했다.

둘을 모두 줄이기 위해서 방법을 고민하다가 두 과정을 한 번에 하기 위해서 알고리즘 리스트의 쓰임을 다르게 하였다!

마지막에 오타를 못 찾아서 한참의 문제가 헤맸다..😭

💻 코드

import sys
input = sys.stdin.readline

N, K, D = map(int, input().split())
# 학생들의 정보 => 학생 실력, 알고있는 알고리즘
students = []
# 해당 알고리즘 아는 학생 수
algorithms = [0 for _ in range(K+1)]

for _ in range(N):
    student = [int(input().split()[-1])]
    student.append(list(map(int, input().split())))
    students.append(student)
students.sort()

start, end, E = 0, 0, 0

while start < N:
    while end < N and students[end][0] - students[start][0] <= D:
        for i in students[end][1]:
            algorithms[i] += 1
        end += 1
        
    anyKnows, allKnows = 0, 0
    for i in range(1, K+1):
        if algorithms[i] != 0:
            if algorithms[i] == end - start:
                allKnows += 1
            anyKnows += 1
            
    E = max(E, (anyKnows - allKnows) * (end - start))
    
    for i in students[start][1]:
        algorithms[i] -= 1
    start += 1
    
print(E)