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

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

22233번: 가희와 키워드

22233, 가희와 키워드

[ 난이도 : 실버 2 ]

이번 문제는 시간복잡도를 잘 고려해주어야 한다.

 

N과 M의 범위가 2 X 10^5 까지이다. ArrayList 의 contains 를 사용한 풀이를 했을 때는 시간 초과가 발생할 수 있다.

그렇기 때문에 HashMap 을 사용한 풀이에 대해 설명해보겠다.

# Process

Input

static int N, M, cnt;
static HashMap<String, Boolean> words = new HashMap<>();

static void input() 
{
    N = scan.nextInt(); M = scan.nextInt(); cnt = N;
    while(N-->0) words.put(scan.nextLine(), true);
}

 

Process

: HashMap 에 ContainsKey() 를 사용하였다.

containskey() 의 시간 복잡도는 1 이다.

while(M-- > 0)
{
    st = new StringTokenizer(scan.nextLine(), ",");
    while(st.hasMoreTokens())
    {
        String w = st.nextToken();
        if(words.containsKey(w))
        {
            words.remove(w);
            cnt--;
        }
    }

    sb.append(words.size()+"\n");
}

System.out.println(sb);

 

전체 코드

: HashMap 과 ContainsKey 를 사용하면 간단하게 풀 수 있지만 시간과 메모리는 크게 잡아먹는 것 같아서

다른 풀이도 찾으면 공유하겠다.

static StringTokenizer st;

static int N, M, cnt;
static HashMap<String, Boolean> words = new HashMap<>();

static void input() 
{
    N = scan.nextInt(); M = scan.nextInt(); cnt = N;
    while(N-->0) words.put(scan.nextLine(), true);
}

static void pro()
{
    while(M-- > 0)
    {
        st = new StringTokenizer(scan.nextLine(), ",");
        while(st.hasMoreTokens())
        {
            String w = st.nextToken();
            if(words.containsKey(w))
            {
                words.remove(w);
                cnt--;
            }
        }

        sb.append(words.size()+"\n");
    }

    System.out.println(sb);
}   

public static void main(String[] args) 
{
    input();
    pro();
}