[백준 22233] 가희와 키워드 (JAVA)

백준(BOJ) 22233 가희와 키워드

 

난이도
221224 기준 실버 2

사용 알고리즘
자료구조(HashMap)

문제 링크
https://www.acmicpc.net/problem/22233

22233번: 가희와 키워드

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

가희는 블로그를 운영하고 있습니다. 가희는 블로그에 글을 쓰기 위해, 메모장에 키워드를 적곤 합니다.

지금까지 메모장에 써진 키워드는 모두 서로 다르며, 총 N개가 존재합니다.

가희는 새로운 글을 작성할 때, 최대 10개의 키워드에 대해서 글을 작성합니다.

이 키워드들 중에 메모장에 있었던 키워드는 가희가 글을 쓴 이후, 메모장에서 지워지게 됩니다.

가희는 블로그에 글을 쓰고 나서, 메모장에 있는 키워드 개수가 몇 개인지 알고 싶습니다. 가희를 도와주세요.

 

 

입력

첫 번째 줄에 가희가 메모장에 적은 키워드 개수 N, 가희가 블로그에 쓴 글의 개수 M이 공백으로 구분해서 주어집니다.

2번째 줄부터 N+1번째 줄까지 메모장에 적은 키워드 N개가 주어집니다.

N+2번째 줄부터 N+M+1번째 줄까지, 가희가 쓴 글과 관련된 키워드가 , (쉼표)로 구분해서 주어집니다. 공백으로 구분되지 않음을 유의해 주세요.

 

출력

 x번째 줄에는 x번째 글을 쓰고 난 후에 메모장에 남아 있는 키워드의 개수를 출력해 주세요.

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 시간 복잡도를 낮출 수 있는 적절한 자료구조를 사용해서 문제를 풀면 되겠네요. 숫자 인덱스로 검색하는게 아니라 String 키워드로 검색하는 경우 저는 보통 HashMap 부터 떠올립니다. HashMap을 처음 보시는 분이라면 검색해서 공부해보세요 알고리즘 문제 풀 때 여기저기 쓸 일이 많습니다.

 

 

3. 풀이 구상

 

 처음에 가희의 메모장에 있는 키워드들을 key로 HashMap에 전부 집어 넣고 value로는 1을 넣어주겠습니다.

 가희가 블로그에 글을 쓰고 작성한 키워드들을 HashMap에서 검색하고 value가 1이라면 1을 0으로 바꿔주고 메모장에 남아있는 키워드의 개수를 1 줄여주는 방식으로 문제를 풀어가면 될 것 같습니다.

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

// 백준 22233 가희와 키워드
public class Main {

	static int N, M;
	static HashMap<String, Integer> hm;
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());

    	hm = new HashMap<>();
    	
    	for(int i = 0; i < N; i++) {
    		String str = br.readLine();
    		hm.put(str, 1);
    	}
    	
    	int result = N;
    	
    	for(int i = 0; i < M; i++) {
    		String str = br.readLine();
    		String[] strarr = str.split(",");
    		
    		for(int j = 0, size = strarr.length; j < size; j++) {
    			String cur = strarr[j];
    			if(hm.containsKey(cur) && hm.get(cur)==1) {
    				result--;
    				hm.replace(cur, 0);
    			}
    		}
    		
    		bw.write(result+"\n");
    	}
    	
    	bw.flush();
        bw.close();
        br.close();
    }
    	

}

 

2. 주의할 점

 

 HashMap에 대한 이해만 있으면 딱히 주의할 점은 없는 것 같습니다.

 

 

풀이 후기

 기업 코딩테스트들에 Map을 사용하고 문자열을 parsing 하는 문제들이 자주 나오는 것 같아 한번 풀어봤습니다. 문자열 관련 알고리즘도 슬슬 하나씩 공부해나가야겠네요