| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 633 | 117 | 90 | 18.443% |
가희는 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×1051 ≤ r ≤ 105features의 길이 총합은 2×106을 넘어가지 않습니다. 이때, 구분자 ,는 길이 총합에서 제외됩니다.U 요청에 나타난 모든 특징의 종류는 1개 이상 9개 이하입니다.G 요청은 하나 이상 주어집니다.3 Daredemo Daisuki original 4 U Daredemo kami U original ittkii,kami G kami,ittkii G kami
1 2
2번의 U 요청이 이루어지고 난 후 각 역의 특징은 표 1과 같습니다.
[표 1] 2번의 U 요청이 이루어진 후 역들의 특징
먼저, ittkii와 kami라는 특징을 가진 역의 개수를 구하라는 요청이 들어왔습니다. Daisuki역 하나만 있으므로, 1을 출력합니다.
다음에 특징 kami를 가진 역의 개수를 구하라는 요청이 들어왔습니다. Daredemo역과 original역은 특징 kami가 있습니다. 따라서 다음 줄에 2를 출력합니다.
4 sadang sindorim jamsil sillim 6 U jamsil hell U sindorim hell G hell U sindorim veryhell G hell G hell,line3
2 1 0
2번의 U 요청이 이루어지고 난 후 각 역의 특징은 [표 2]와 같습니다.
[표 2] 2번의 U 요청이 이루어진 후 예제에 주어진 역의 특징
2번의 U 요청이 들어온 후, hell라는 특징을 가진 역의 개수를 구하라는 요청이 들어왔습니다. sindorim역과 jamsil역이 있으므로, 2를 출력합니다.
그 다음에 sindorim역의 특징을 veryhell로 업데이트 하라는 요청이 들어왔습니다. 이 요청이 수행된 후 상태는 [표 3]과 같습니다.
[표 3] sindorim역의 특징을 hell에서 veryhell로 업데이트 한 후
따라서, 특징 hell을 가진 역은 jamsil역 1개가 됩니다.
그 다음 요청은 특징 hell과 특징 line3을 가진 역의 개수를 구하는 것입니다. 특징 line3을 가지는 역은 없으므로 0을 출력합니다.
3 sindae rella NEWYOrK 2 G sosen,kyo G sale
0 0
역 특징을 업데이트 하는 요청이 하나도 없습니다. 따라서 sosen과 kyo특징을 모두 가지는 역은 없습니다. 그리고 sale이라는 특징을 가지는 역도 없습니다.
5 sosen kyomo akihabara kyoto tanoshides 8 U sosen 200kai,renzoku U kyomo ranking,increase U tanoshides kore,wa,creazyyy,increase G increase U kyoto ranking,creazyyy G Is,kyoto,near,from,tokyo U akihabara creazyyy,ranking G creazyyy,ranking
2 0 2
4 Shippo saransaran shimai shinagara 8 U saransaran watashi,wa U shimai unni,juin G juin U shinagara oppa,juin,manae U Shippo oppa,manae G manae,oppa U shinagara unnee G oppa,manae
1 2 1
5 Hello bye wrong time nosee 5 U Hello What,are,you,doing,today G doing,What U nosee today,Noway,venus,bye G today G today,doing
1 2 1
4 Its my trap card 5 U trap gahui,ga U trap hori U card ssgt U trap saea,trap G trap
1
2개의 U 요청이 아래와 같았다고 해 보겠습니다.
U a,b,c,d,e,f,gU h,i,j,k이러한 요청은 들어오지 않습니다. 전체 U 업데이트에 사용된 모든 특징의 종류가 a,b,c,d,e,f,g,h,i,j,k로 11개이기 때문입니다.
또한, G 요청은 U 요청에 나오지 않은 특징이 나올 수 있습니다. [예제 2]는 이를 보여줍니다.
Contest > BOJ User Contest > 가희와 함께 하는 코딩 테스트 > 가희와 함께 하는 5회 코딩테스트 F번