20438. 출석체크

문제

백준 20438번 출석체크

---

풀이

먼저 값들을 모두 입력받는다.
sleep은 졸고 있는 학생들 리스트, recv는 출석코드를 받은 학생들 리스트

그리고 출석체크를 할 리스트 check를 만들어주는데 학생번호를 3부터 n+2까지 부여한다고 했으므로 편의상 0부터 n+2까지 값을 만든다.

check = [i for i in range(n+3)]

코드를 받은 학생을 순차적으로 탐색하면서 출석체크를 하는데,
stu가 자고있는 학생이면 -> 스킵
아니면 -> while문을 통해 다음 학생 nxt 체크. 이 때 자고 있는 학생이면 체크하지 않는다.

for stu in recv:
    if stu in sleep: continue
    nxt = stu
    while nxt <= n+2:
        if nxt not in sleep: check[nxt] = 0 
        nxt += stu

마지막으로 m개의 줄에 각 구간별 출석체크가 안 된 학생을 출력한다.
check[i] == 0이 출석된 것이기 때문에 구간 길이에서 0인 학생수를 뺀다.

print(e - s + 1 - check[s:e+1].count(0))

전체코드

import sys

n, k, q, m = map(int, sys.stdin.readline().split())
sleep = list(map(int, sys.stdin.readline().split()))
recv = list(map(int, sys.stdin.readline().split()))

check = [i for i in range(n+3)]
for stu in recv:
    if stu in sleep: continue
    nxt = stu
    while nxt <= n+2:
        if nxt not in sleep: check[nxt] = 0 
        nxt += stu

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(e - s + 1 - check[s:e+1].count(0))

---

근데 이상한게 좀 더 가독성있게 바꾸려고 check[i] == 1이 출석된 걸로 바꿔서 채점 돌렸는데 시간초과가 났다.

import sys

n, k, q, m = map(int, sys.stdin.readline().split())
sleep = list(map(int, sys.stdin.readline().split()))
recv = list(map(int, sys.stdin.readline().split()))

check = [0 for _ in range(n+3)]  ## -> 0으로 수정
for stu in recv:
    if stu in sleep: continue
    nxt = stu
    while nxt <= n+2:
        if nxt not in sleep: check[nxt] = 1 ## 출석체크
        nxt += stu

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(check[s:e+1].count(0)) ## 0을 카운트
    

왜그러는지 이유를 찾아봐야겠다..
--> 채점케이스에 출석이 안된 학생들이 많은 케이스가 있어서 check[s:e+1].count(0) 이 부분에서 시간 초과가 나는 것 같다.

---

+) 개선

누적합 문제였다

앞서 내가 푼 방법은 시간복잡도가 O(M*N)인데,
누적합으로 풀면 O(M+N)으로 개선할 수 있다.

check[i] == 1을 출석완료로 변경했고

check = [0 for _ in range(n+3)]
for stu in recv:
    if stu in sleep: continue
    nxt = stu
    while nxt <= n+2:
        if nxt not in sleep: check[nxt] = 1
        nxt += stu

check를 다시 출석이 된 학생들을 누적한 리스트로 변경했다.

for i in range(4, n+3): check[i] += check[i-1]

구간길이에서 해당 구간의 출석완료된 학생들을 빼준 값을 출력한다.

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(len(check[s:e+1]) - (check[e] - check[s-1]))

아래와 같이 시간이 개선됐다.

개선된 전체코드

import sys

n, k, q, m = map(int, sys.stdin.readline().split())
sleep = list(map(int, sys.stdin.readline().split()))
recv = list(map(int, sys.stdin.readline().split()))

check = [0 for _ in range(n+3)]
for stu in recv:
    if stu in sleep: continue
    nxt = stu
    while nxt <= n+2:
        if nxt not in sleep: check[nxt] = 1
        nxt += stu

for i in range(4, n+3): check[i] += check[i-1]
for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(len(check[s:e+1]) - (check[e] - check[s-1]))