[Java] 가희와 키워드 [22233번]

 

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

• 예제 입력1

5 2
map
set
dijkstra
floyd
os
map,dijkstra
map,floyd

• 예제 출력1

3
2

• 예제 입력2

2 2
gt26cw
1211train
kiwoom,lottegiant
kbo

• 예제 출력2

2
2

---

• 문제 접근
  • N개의 키워드가 메모장에 적혀있음
  • 글 1개당 최대 10개의 키워드 사용 가능
  • 2 ~ N + 1번 줄까지는 메모장의 키워드
  • N + 2 ~ N + M + 1번 줄까지는 쓴 글과 관련된 키워드가 쉼표( , )로 입력
• 문제 해결
  • N은 최대 20만으로 배열로 하면 메모리 초과가 나올 것으로 예상
  • 메모장의 키워드는 중복되지 않기에 Set으로 저장
  • 글에 사용된 키워드를 반복문을 사용하여 Set 안에서 삭제
  • 글 하나 입력 시 마다 메모장에 남은 키워드(Set.size) StringBuilder에 저장

• 슈도 코드

Set 선언
memoCnt(메모장 키워드 개수), blogArticleCnt(블로그 게시글 개수)
for(memoCnt만큼 반복){
	Set에 추가
}

for(blogArticleCnt){
	input[] (게시글 키워드 저장)
	for(input[] 길이만큼 반복){
		if(input[j]가 Set에 포함된다면)
			Set에서 제거
	}
	Set 크기 출력
}

• 코딩하기

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Set<String> keyword = new HashSet<>();
    String[] input = br.readLine().split(" ");
    int memoCnt = Integer.parseInt(input[0]); // 메모장 키워드 개수
    int blogArticleCnt = Integer.parseInt(input[1]); // 게시글 개수
    for(int i = 0; i < memoCnt; i++){
        keyword.add(br.readLine()); // 메모장 키워드 Set에 저장
    }
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < blogArticleCnt; i++){
        input = br.readLine().split(",");
        for(String word : input){
            keyword.remove(word);
        }
        sb.append(keyword.size()).append("\n");
    }
    System.out.println(sb);
}