회상_백준32953

 

<문제>

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

 

<시간 초과 풀이>

import sys

input = sys.stdin.read().splitlines()
N, M = map(int, input.pop(0).split())

dict = {}
all_student = set([])
all_class = []
result = 0

for i in range(1, 2 * N, 2):
    c_list = input[i].split()

    all_student.update(c_list)
    all_class.append(c_list)

for s in all_student:
    count = 0

    for c in all_class:
        if s in c:
            count += 1

    if count >= M:
        result += 1

print(result)

 

- 단순하게 풀면 왠지 성능때문에 안될 것 같았지만 일단 해봄

- 전체 학번을 set으로 만들어서 중복 없앰 -> 전체 학번 set

- 수업 리스트를 묶은 리스트 (2차 배열)

- 전체 학번 set 순회, 전체 수업 리스트 순회, 각 수업 리스트 순회 -> 이제 보니 3중으로 for문이었네

 

 

<통과 풀이>

import sys

input = sys.stdin.read().splitlines()
N, M = map(int, input.pop(0).split())

all_student = set([])
all_class = []
result = 0

for i in range(1, 2 * N, 2):
    c_list = input[i].split()
    all_student.update(c_list)
    
    c_dict = { s: 1 for s in c_list }
    all_class.append(c_dict)

for s in all_student:
    count = 0

    for c in all_class:
        if s in c:
            count += 1

    if count >= M:
        result += 1

print(result)

 

- 해시테이블을 이용하면 조회 시간이 빨라짐 O(1)

- 두번째 for 문에서 전체 학번 set을 순회, 전체 수업 리스트를 순회하는 것 같지만 하나의 수업에서 학번을 찾는 것은 해시테이블에서 찾음

- 만약 통과가 안됐다면 중첩된 for문을 다시 바꾸는 방법을 찾아야 했을 듯

 

<더 깔끔한 방법>

import sys
input = sys.stdin.readline
ha = dict()
N, M = map(int, input().split())
for i in range(N):
    K = int(input())
    for j in list(map(int, input().split())):
        if j in ha : ha[j] += 1
        else : ha[j] = 1

cnt = 0
for i in ha:
    if ha[i] >= M:
        cnt += 1

print(cnt)

 

- 다른 사람 풀이

- 그냥 해시테이블에 라인을 읽으면서 +1 씩 추가하면 됐구나