[백준] java 7785 회사에 있는 사람

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

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

(현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.)

접근 과정 / 풀이 과정

간단한 문제인 것 같다. 중복된 이름을 갖고있는 사람이 없으므로 처음 로그에 남은 사람이면 집합에 추가하고 두 번째 로그에 찍힌 사람이면 집합에서 제거한다.

HashSet을 이용하여 어렵지않게 해결했다. 출력 시에 HashSet에 있는 데이터를 자바 스트림으로 변환하여 정렬 후 BufferedWriter을 사용하여 출력하였다.

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		// 출입한 인원 수
		int n = Integer.parseInt(br.readLine());
		// 해시셋
		Set<String> set = new HashSet<>();

		for( int i = 0; i < n; i++ ){

			st = new StringTokenizer(br.readLine(), " ");

			String memberName = st.nextToken();

			// set에 사원 명이 포함 되어 있으면 삭제
			if( !set.add( memberName ) )
				set.remove( memberName );

		}

		set.stream().sorted( (a,b) -> b.compareTo(a) ).forEach( e -> {
			try {
				bw.write(e+"\n");
			} catch (IOException ex) {
				throw new RuntimeException(ex);
			}
		});
		bw.flush();

	}
}

생각할 점

한 가지를 고민했다.

문제에서 마지막 출력 시에 회사에 남아있는 사람을 사전의 역순으로 출력하는 것이다. 그렇다면 항상 정렬을 유지해주는 자료구조인 이진 트리를 고려해볼법하다. 정렬을 유지해주니 내가 제출한 풀이에서, 마지막에 따로 스트림으로 변환하기 위한 메모리 할당과 정렬 메서드를 사용할 필요가 없다.

위의 소스코드와 TreeSet을 사용한 소스코드의 속도를 비교해보자.
[ TreeSet ]

public static void solved() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		// 출입한 인원 수
		int n = Integer.parseInt(br.readLine());
		TreeSet<String> tree = new TreeSet<>( (o1, o2) ->  o2.compareTo(o1)  );
		for( int i = 0; i < n; i++){
			st = new StringTokenizer(br.readLine(), " ");
			String memberName = st.nextToken();
			if( !tree.add( memberName ))
				tree.remove( memberName );
		}
		Iterator<String> it = tree.iterator();
		while( it.hasNext() ){
			bw.write( it.next() );
			bw.newLine();
		}
		bw.flush();
	}

코드는 위와같이 구현했으며 속도 차이는 다음과 같다.

TreeSet : 588ms , HashSet : 708ms

TreeSet 자료구조를 사용했을 때의 결과가 더 좋았다.