7057 : 역색인 (Inverted Index) 만들기
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
역색인(Inverted Index)은 문서 검색 엔진에서 특정 단어가 어느 문서들에 나타나는지를 빠르게 찾을 수 있도록 돕는 핵심 자료구조입니다.
여러 개의 텍스트 문서가 주어졌을 때 각 단어별로 해당 단어가 나타나는 문서 번호(0번부터 시작)들의 집합을 매핑하는 역색인을 구축하고, 검색어 쿼리에 대한 결과를 반환하는 프로그램을 작성하십시오.
[제약 조건]
• 문서 수 $N$: $1 \le N \le 100$
• 쿼리 수 $Q$: $1 \le Q \le 100$
여러 개의 텍스트 문서가 주어졌을 때 각 단어별로 해당 단어가 나타나는 문서 번호(0번부터 시작)들의 집합을 매핑하는 역색인을 구축하고, 검색어 쿼리에 대한 결과를 반환하는 프로그램을 작성하십시오.
[제약 조건]
• 문서 수 $N$: $1 \le N \le 100$
• 쿼리 수 $Q$: $1 \le Q \le 100$
입력 설명
첫째 줄에 문서의 수 N이 주어집니다. (1 ≤ N ≤ 100)
둘째 줄부터 N개의 줄에 걸쳐 각 문서의 내용이 공백으로 구분된 소문자 단어들로 주어집니다.
이후 다음 줄에 검색어 쿼리의 수 Q가 주어집니다. (1 ≤ Q ≤ 100)
그 다음 줄부터 Q개의 줄에 걸쳐 검색하고자 하는 단어가 한 줄에 하나씩 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 각 문서의 내용이 공백으로 구분된 소문자 단어들로 주어집니다.
이후 다음 줄에 검색어 쿼리의 수 Q가 주어집니다. (1 ≤ Q ≤ 100)
그 다음 줄부터 Q개의 줄에 걸쳐 검색하고자 하는 단어가 한 줄에 하나씩 주어집니다.
출력 설명
Q개의 줄에 걸쳐 각 검색어가 포함된 문서 번호(0-based)를 오름차순으로 정렬하여 공백으로 구분해 출력합니다.
만약 해당 단어가 어떤 문서에도 존재하지 않으면 빈 줄을 출력합니다.
만약 해당 단어가 어떤 문서에도 존재하지 않으면 빈 줄을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
i love python
python is fun
you love coding
3
love
python
java
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0 2
0 1
도움
딕셔너리의 값으로 집합(set)을 가지는 구조를 활용해 보십시오. 파이썬의
collections.defaultdict(set)를 사용하면 역색인을 편리하게 빌드할 수 있습니다.