[Java] 회사에 있는 사람 [7785번]

• 예제 입력1

4
Baha enter
Askar enter
Baha leave
Artem enter

• 예제 출력1

Askar
Artem

---

• 문제 접근
  • 출입 기록의 수가 최대 10$^6$이므로 시간 복잡도가 O(N$^2$)이면 1조로 시간 초과
  • enter와 leave가 찍힌 사원은 퇴근한 사원
  • 대소문자가 다른 경우 다른 사람
• 문제 해결
  • 동명이인이 없으니 Set으로 저장하고 한 번 더 나올 경우 삭제

• 슈도 코드

N(출입 기록 개수)
Set overWork(직원 저장 자료구조)
for(N번 반복){
	emp에 직원 이름만 저장
	if(overWork에 포함된 직원이면){
		제거
		continue;
	}
	set에 추가
}
set에 있는 직원 전체 출력

• 코딩하기

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Set<String> overWork = new HashSet<>();
    int N = Integer.parseInt(br.readLine());
    for(int i = 0; i < N; i++){
        String employee = br.readLine().split(" ")[0];
        if(overWork.contains(employee)){ // set에 있을 경우 삭제
            overWork.remove(employee);
            continue;
        }
        overWork.add(employee); // 없을 경우 추가
    }
    List<String> overWorkList = new ArrayList<>(overWork); // 리스트로 변경
    Collections.sort(overWorkList, Comparator.reverseOrder()); // 역순 정렬
    StringBuilder sb = new StringBuilder();
    for (String emp : overWorkList) {
        sb.append(emp).append("\n");
    }
    System.out.println(sb);
}