[백준] 25192 : 인사성 밝은 곰곰이

인사성 밝은 곰곰이 링크

문제 핵심을 보면 다음과 같다.
1. 문제에서 ENTER를 만나면 새로 인식을 한다.
2. 한 번 입력된 닉네임은 다시 들어왔을 때 카운트되지 않는다.
3. 이 둘을 합치면, 처음의 닉네임은 카운트되고 이후에는 카운트되지 않으나, ENTER가 들어왔을 때는 처음으로 인식한다.

이 문제를 보면서, 그냥 Queue를 하나 만들어 관리하면 되지 않나? 부터 생각이 들었다.
먼저, ENTER를 만났으면, 카운트하지 않고 그대로 지나가고,
그 외 문자면 다음과 같은 논리 전개를 한다.
1. 현재 받은 문자열이 큐에 포함되어 있으면 넘긴다.
2. 그렇지 않다면 큐에 새로 추가하고, 카운트한다.

코드는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main_bj_25192_인사성밝은곰곰이 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int cnt = 0;
        Queue<String> queue = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            String chat = br.readLine();
            if (chat.equals("ENTER")) {
                queue.clear();
                continue;
            } else {
                if (queue.contains(chat)) {
                    continue;
                } else {
                    queue.add(chat);
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }
}

테스트를 해봤을 때 출력이 잘 나오길래 그대로 제출을 했다.

그러나 시간초과가 난다.
이유는 아마, 반복문을 돌면서 큐에 있는 문자열이 지금 받은 문자열과 일치하는지를 계속 하기 때문에 시간 초과가 발생했을 것 같다.
이를 해결하기 위해 Queue에서 계속 찾아내는 것이 아닌, HashSet을 사용해보고자 했다.

import java.io.*;
import java.util.*;

public class Main_bj_25192_인사성밝은곰곰이 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int cnt = 0;
        HashSet<String> set = new HashSet<>();

        for (int i = 0; i < N; i++) {
            String chat = br.readLine();

            if (chat.equals("ENTER")) {
                set.clear();
            } else {
                if(!set.contains(chat)) {
                    set.add(chat);
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }
}

다를게 없다.
하지만 Queue를 사용했을 때 시간복잡도가 O(N)인 것에 반해, HashSet을 사용하게 되면 O(1)이 된다.

Queue는 데이터를 순차적으로 탐색하는데 반해, HashSet은 해시 함수로 바로 접근하기 때문이다.
즉, 모든 것을 다 탐색해보는 Queue와 직접 찾아가는 HashSet은 이 정도의 시간복잡도의 차이가 난다고 보면된다.

보면 결과도 잘 나오는 것을 확인할 수 있다.