[백준] 20438번: 출석체크 (Python)

문제

20438번: 출석체크

 

풀이 코드 1

• 처음엔 출석 학생부터 누적합을 어떻게 활용해야 하나 고민했는데, 누적합에 대한 개념이 제대로 안섰나보다.
• 구간 M <= 50000 이므로 미참석자수를 표시 할 때 아래와 같은 코드로 하면 시간초과

import sys
input = sys.stdin.readline
N, K, Q, M = map(int, input().split())

ks = set(map(int, input().split()))
qs = set(map(int, input().split()))
ms = []
for _ in range(M):
    s, e = map(int, input().split())
    ms.append((s, e))
# 1. 출석 학생 표시
visited = [0] * (N + 3)
for q in (qs - ks):
    for i in range(q, N + 3, q):
        if i not in ks:
            visited[i] = 1

# 2. 미참석자수 표시
for s, e in ms:
	print(visited[s:e+1].count(0))

풀이  코드 2

• 누적합 부분은 풀이 참고 했음.
• 이전의 visited[s:e+1].count 로 인해 이중 for 문과 같은 시간 복잡도를 가지지 않고,
• 누적합을 통해 for문 1개로 끝낼 수 있어 시간 초과에 걸리지 않는다. 

import sys
input = sys.stdin.readline
N, K, Q, M = map(int, input().split())

ks = set(map(int, input().split()))
qs = set(map(int, input().split()))
ms = []
for _ in range(M):
    s, e = map(int, input().split())
    ms.append((s, e))
# 1. 출석 학생 표시
visited = [0] * (N + 3)
for q in (qs - ks):
    for i in range(q, N + 3, q):
        if i not in ks:
            visited[i] = 1

# 2. 미참석자 수 합치는 단계 -> 누적합
attend = [0] * (N + 3)
for i in range(3, N + 3):
    if not visited[i]:
        attend[i] = attend[i-1] + 1
    else:
        attend[i] = attend[i-1]
        
# 3. 답 프린트
answer = []
for s, e in ms:
    answer.append(attend[e] - attend[s-1])

for a in answer:
    print(a)