[백준 JAVA] 19583 싸이버개강총회

19583 싸이버개강총회 

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

문제설명

스트리밍에서 특정 시간 범위에 참석한 사람들을 찾는다.

1. S: 시작 시간
2. E: 종료 시간
3. Q: 질문 시간

여러 사람의 출입 기록이 주어지며 각 기록은 시간과 이름으로 이루어져 있다.

S 시간 이전에 이벤트에 참석한 사람들 중 E 시간 이후 Q 시간 이전에도 참석한 사람들의 수를 세는 것이다.

문제풀이

 

• Set 사용:
  • S 시간 이전에 들어온 사람들의 이름을 저장한다.
  • E 시간 이후 Q 시간 이전에 들어온 사람들의 이름을 저장한다.
  • 모든 참석자의 이름을 저장한다.
• 시간 비교:
  • 각 기록의 시간과 S, E, Q를 비교하여 적절한 Set에 이름을 추가한다.
  • Set에 모두 포함된 사람의 수를 세어 출력한다.

 

O(N+M)  시간복잡도

• 입력 처리: 각 출입 기록을 한 번씩 읽으므로 O(N)이다. 여기서 N은 입력된 기록의 수이다.
• Set의 탐색 및 삽입: Set에 삽입과 탐색을 수행하는데 상수 O(1)의 시간 복잡도를 가진다.
• 결과 계산: nameSet에 있는 모든 이름을 확인하므로 O(M)입니다. 여기서 M은 서로 다른 참석자의 수이다.

전체 알고리즘의 시간 복잡도는 O(N + M)이다.

전체코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String S = st.nextToken();
        String E = st.nextToken();
        String Q = st.nextToken();

        Set<String> before = new HashSet<>();
        Set<String> after = new HashSet<>();
        Set<String> nameSet = new HashSet<>();
        String str = null;

        while((str = br.readLine()) != null) {
            String[] arr = str.split(" ");
            String time = arr[0];
            String name = arr[1];

            nameSet.add(name);
            if(S.compareTo(time) >= 0) {
                before.add(name);
            }else if(E.compareTo(time) <= 0 && Q.compareTo(time) >= 0) {
                after.add(name);
            }
        }

        int ans = 0;
        for(String name : nameSet) {
            if(before.contains(name) && after.contains(name)) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}