백준27888 가희와 지하철역 저장 시스템 1 [python]

문제: https://www.acmicpc.net/problem/27888

 

문제

 

가희는 n개의 지하철역 정보를 보기 위한 시스템을 만들었습니다. 이 시스템은 정말 단순하게 동작합니다.

• 유저가 역 station의 특징을 한 번도 업데이트하지 않은 경우, 역 station의 특징은 없습니다.
• 각 역은 유저들이 업데이트한 특징이 있습니다. 예를 들어, deepstation, longescalator, dungeon과 같은 것들입니다.
• deepstation, longescalator, dungeon과 같은 특징을 입력했을 때 조건에 맞는 역들이 나타나게 됩니다.

그런데 사용하는 유저가 많아질수록 가희가 만들어 놓은 시스템이 느려지기 시작했습니다. 가희를 도와주세요.

입력

첫 번째 줄에 n이 주어집니다.

다음 n개의 줄에 역 이름이 한 줄에 하나씩 주어집니다.

다음 줄에 요청의 개수 r이 주어집니다.

다음 r개의 줄에 요청이 다음 형식 중 하나로 주어집니다.

• U station features
  • 역 station의 특징을 features로 업데이트합니다.
• G features
  • features의 특징을 모두 가진 역의 개수를 출력합니다.

이때 features는 특징이 여러 개인 경우 콤마(,)로 구분되어 주어집니다. 또한 중복된 특징은 주어지지 않습니다.

station은 주어진 n개의 지하철역 이름 중 하나입니다..

예를 들어, soongsiluniv역의 특징을 line7과 deep으로 업데이트 하려는 경우 요청은 아래와 같이 주어집니다.

U soongsiluniv line7,deep

또한 특징 beautiful과 dungeon이라는 특징을 가지는 역의 개수를 구하라는 요청은 아래와 같이 주어집니다.

G beautiful,dungeon

출력

조건을 만족하는 역의 개수를 구하라는 요청이 들어올 때마다 한 줄에 하나씩 답을 출력해 주세요.

제한

• 1 ≤ n ≤ 5×10⁵
• 1 ≤ r ≤ 10⁵
• 주어지는 역명의 길이는 1 이상 10 이하이며, 역명은 중복되지 않습니다. 역명은 알파벳 대소문자와 숫자로만 이루어져 있습니다.
• 요청에 주어지는 features의 길이 총합은 2×10⁶을 넘어가지 않습니다. 이때, 구분자 ,는 길이 총합에서 제외됩니다.
• 전체 U 요청에 나타난 모든 특징의 종류는 1개 이상 9개 이하입니다.
• 특징은 알파벳 대소문자와 숫자로만 이루어져 있으며, 길이는 1 이상 10 이하입니다.
• G 요청은 하나 이상 주어집니다.

힌트

2개의 U 요청이 아래와 같았다고 해 보겠습니다.

• U a,b,c,d,e,f,g
• U h,i,j,k

이러한 요청은 들어오지 않습니다. 전체 U 업데이트에 사용된 모든 특징의 종류가 a,b,c,d,e,f,g,h,i,j,k로 11개이기 때문입니다.

또한, G 요청은 U 요청에 나오지 않은 특징이 나올 수 있습니다. [예제 2]는 이를 보여줍니다.

 

문제풀이

문제 풀이 아이디어

입력 받은 역의 특징들의 교집합의 개수를 출력하는 문제이다.

제한과 힌트를 보면 알겠지만 모든역의 특징의 개수의 합은 9개 이하이다. 그럼 비트마스킹을 떠올릴수 있다.

예를 들어보자, A역에는 1,2,3의 특징을 가지고 있고, B역에는 1,3,4의 특징을 가지고 있다.

그럼 A역는 1110으로 나타낼수 있고 B역은 1011으로 나타낼수 있다. 이렇게되면 비트 &연산자를 통해 빠르게 교집합의 개수를 구할수 있다.

 

1. 역들을 dict에 저장한다.

2. U요청이 들어오면 각 특징들의 비트위치를 저장하면서, 역의 특징들을 업데이트한다 .

3. G요청이 들어오면 요청특징의 비트위치를 모두 찾고 &연산자로 교집합의 개수를 구한다.

 

구현

기본 입력처리

def main():
    b=0
    st={input().strip():int("0",2) for _ in range(int(input()))}

 

쿼리 처리 - U

def main():
    c,*p=input().strip().split()
    if c=="U":
        sn=p[0]#역명
        if db.get(st[sn],0): #역의 정보를 받았던 적이 있으면 내용 초기화
            db[st[sn]]-=1 
        sf=p[1].split(",") #역 특징을 파싱
        kb=["0"]*10
        for k in sf:
            try:
                kb[sp[k]]="1"
            except: #특징의 비트정보가 없으면 비트위치를 생성 및 저장
                sp[k]=b
                b+=1
                kb[sp[k]]="1"
        p=int("".join(kb),2)
        st[sn]=p #역에 비트정보를 저장
        try:
            db[p]+=1 #비트 정보에 역의 개수 저장
        except:
            db[p]=1

 

쿼리 처리-G

def main():
    c,*p=input().strip().split()
    elif c=="G":
        jb=["0"]*10
        for j in p[0].split(","):
            try:
                jb[sp[j]]="1"
            except: #요청 특징이 비트 정보dict에 없으면 무조건 교집합의 수는 0이다.
                print(0)
                break
        else:
            p=int("".join(jb),2)
            ans=0
            for i in db.keys(): #많아야봐야 2^9 -> 512번 탐색
                if i&p==p: #특징을 모두 교집합으로 가지는 비트라면 정답에 역의 개수 추가
                    ans+=db[i]
            print(ans)

 

전체코드

input=open(0).readline
sp={}
db={}
def main():
    b=0
    st={input().strip():int("0",2) for _ in range(int(input()))}
    for _ in range(int(input())):
        c,*p=input().strip().split()
        if c=="U":
            sn=p[0]
            if db.get(st[sn],0):
                db[st[sn]]-=1
            sf=p[1].split(",")
            kb=["0"]*10
            for k in sf:
                try:
                    kb[sp[k]]="1"
                except:
                    sp[k]=b
                    b+=1
                    kb[sp[k]]="1"
            p=int("".join(kb),2)
            st[sn]=p
            try:
                db[p]+=1
            except:
                db[p]=1
        elif c=="G":
            jb=["0"]*10
            for j in p[0].split(","):
                try:
                    jb[sp[j]]="1"
                except:
                    print(0)
                    break
            else:
                p=int("".join(jb),2)
                ans=0
                for i in db.keys():
                    if i&p==p:
                        ans+=db[i]
                print(ans)                    
main()

 

회고

비트마스킹 문제를 처음으로 풀어봤다. 어렵지는 않았지만 태그를 안보고 풀려니 아이디어가 생각이 안났었습니다.

 

문제 태그

#비트마스킹 #자료구조 #해시맵 #문자열 #파싱