Archive / BOJ / Python

14569번 시간표 짜기

이왜틀?

int n=Integer.parseInt(br.readLine());
List<String[]> clas=new ArrayList<>();
for(int i=0;i<n;i++) {
    StringTokenizer st=new StringTokenizer(br.readLine()," ");
    int ntmp=Integer.parseInt(st.nextToken());
    String[] atmp=new String[ntmp];
    int idx=0;
    while(st.hasMoreTokens()) {
        atmp[idx++]=" "+st.nextToken();
    }
    clas.add(atmp);
}

int m=Integer.parseInt(br.readLine());
int[] gn=new int[m];
for(int i=0;i<m;i++) {
    String l=br.readLine();
    if(l.equals("0")) continue;
    else {
        l=l.substring(l.indexOf(' '));
        for(int j=0;j<n;j++) {
            String[] atmp=clas.get(j);
            boolean chk=true;
            for(int k=0;k<atmp.length;k++) {
                if(!l.contains(atmp[k])) {
                    chk=false;
                    break;
                }
            }
            if(chk) gn[i]++;
        }
    }
}
for(int i=0;i<m;i++) bw.write(gn[i]+"\n");

String으로 뭘 해보려했던 것 같은데 넘어가자.

설계

수업시간은 최대 50이니 50비트로 표현할 수 있다.
전부 입력 받아 시간표가 학생의 빈시간에 포함되는지 확인하면 된다.

구현

입력 리스트의 첫 번째 숫자는 뒤에 이어질 숫자의 갯수라 빼고 마스킹해야한다.
이후 교집합을 찾으면 된다.

# 비트마스킹
def masking(n):
    mask = 0
    for i in n:
        mask |= 1 << i

    return mask

N = int(input())
classes = []

for _ in range(N):
   # 첫 숫자 슬라이싱 해야함
   class_time = list(map(int, input().split()))[1:]
   classes.append(masking(class_time))

M = int(input())

for _ in range(M):
    # 첫 숫자 슬라이싱 해야함
    student = masking(list(map(int, input().split()))[1:])
    
    count = 0
    for class_time in classes:
        # 수업 시간과 학생 빈 시간의 교집합
        if class_time & student == class_time:
            count += 1

    print(count)

채점

반성

알고리즘 분류에 비트마스킹이 있어서 그렇게 풀었는데
이거 파이썬 set도 가능할까?
테스트해보자.

N = int(input())

classes = []

# set 써보기
for _ in range(N):
    classes.append(set(map(int, input().split()[1:])))

M = int(input())

for _ in range(M):
    student = set(map(int, input().split()[1:]))
    count = 0
    
    for class_time in classes:
        # subset
        if class_time.issubset(student):
            count += 1

    print(count)

코드 이렇게 하고 제출

오 되네
시간도 나쁘지 않다.
파이썬 set 성능이 우수하다고 들었는데 진짜 그런가보다.
자바 Set의 형언할 수 없는 그 묵직하고 느린 것 때문에 성능에 편견이 있었는데

코드 확인

Link to GitHub