[백준] 회사에 있는 사람 - 7785번

[Silver V] 회사에 있는 사람 - 7785

문제 링크

성능 요약

메모리: 216124 KB, 시간: 1872 ms

분류

자료 구조, 해시를 사용한 집합과 맵

제출 일자

2024년 5월 30일 16:03:53

문제 설명

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

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

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

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 10⁶) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

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

코드

시간 초과 FAIL

시간 복잡도
이 코드의 시간 복잡도는 O(n)입니다. 하나의 반복문을 사용하여 입력으로 받은 사람들의 수에 비례하여 각각의 사람을 처리합니다. 반복문 내에서 각 사람의 이름을 리스트에 추가하고, HashSet에 이름을 추가하면서 중복을 체크하고, 중복된 경우 결과 리스트에서 이름을 삭제합니다. 이 모든 과정은 한 번의 반복문 안에서 처리되므로 시간 복잡도는 O(n)입니다.

공간 복잡도
공간 복잡도는 O(n)입니다. 입력으로 받은 사람들의 수에 비례하여 attendanceRecord, nameList, uniqueNames, result 등의 리스트가 생성됩니다. 이들 리스트의 크기는 모두 입력된 사람들의 수에 비례하므로, 전체적인 공간 복잡도는 O(n)입니다.

package 회사에있는사람;

import java.util.*;

public class Main {


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.nextLine();

        // 4종 과일의 총 합이 5개일 경우 YES 그렇지 않으면 NO
        // 접근1 : HASHMAP으로 풀기
        String[][] attendanceRecord = new String[num][2];

        for (int i = 0; i < num; i++) {
            String strRaw = scanner.nextLine();
            String[] strList = strRaw.split(" ");
            attendanceRecord[i][0] = strList[0];
            attendanceRecord[i][1] = strList[1];
        }

        // 사람 이름 목록
        List<String> nameList = new ArrayList<>(num);
        for(int i = 0; i < num; i++){
            nameList.add(attendanceRecord[i][0]);
        }

        Set<String> uniqueNames = new HashSet<>();
        List<String> result = new ArrayList<>();

        for (String name : nameList) {
            // uniqueNames에 추가할 때 이미 존재하는 이름이라면 result 리스트에 추가하지 않습니다.
            if (uniqueNames.add(name)) {
                result.add(name);
            } else {
                // 이미 존재하는 이름이라면 해당 이름을 리스트에서 삭제합니다.
                result.remove(name);
            }
        }
        result.sort(Comparator.reverseOrder());
        for(String name : result)
            System.out.println(name);
        scanner.close();

    }
}

코드2

시간 & 공간 복잡도
이 코드의 시간 복잡도는 O(n log n)입니다. 여기서 n은 입력으로 주어진 사람들의 수입니다. TreeSet에 요소를 추가하거나 삭제하는 과정에서 내부적으로 이진 검색 트리의 형태를 유지하기 때문에 각각의 연산마다 O(log n)의 시간이 소요됩니다. 따라서 n개의 요소에 대해 TreeSet에 추가하고 정렬하는 데에는 O(n log n)의 시간이 걸립니다.

공간 복잡도는 O(n)입니다. 입력으로 주어진 사람들의 수에 선형적으로 비례하여 TreeSet에 이름이 저장되므로, 공간 복잡도는 O(n)입니다. 추가적으로 사용된 메모리는 상수적이므로 무시할 만큼 작습니다.

package 회사에있는사람;

import java.util.*;

public class Main2 {

    public static void main(String[] args) {

        /**
         * 1. num 변수를 사용하여 처리할 입력의 개수를 결정합니다.
         * 2. TreeSet<String>을 사용하여 이름을 역순으로 정렬하는 TreeSet을 생성합니다.
         *    - 중복을 허용하지 않으므로 중복된 이름은 자동으로 제거됩니다.
         * 3. 입력의 개수만큼 반복하면서 각각의 사람의 이름과 상태를 입력받습니다.
         * 4. 입력된 상태가 "leave"일 경우 해당하는 이름을 TreeSet에서 제거합니다.
         * 5. 입력된 상태가 "leave"가 아닐("enter") 경우 TreeSet에 이름을 추가합니다.
         * 6. TreeSet은 이미 역순으로 정렬되어 있으므로, TreeSet에 저장된 이름을 반복문을 통해 순서대로 출력합니다.
         *
         * 
         *  ================= 잠깐! Comparator.reverseOrder() 알아보기!!!!
         *    해당 메서드는 정적 메서드로, 역순으로 비교를 수행하는 Comparator를 생성합니다.
         *
         *    일반적으로 TreeSet은 기본적으로 요소를 자연 순서(오름차순)로 정렬합니다.
         *    하지만 Comparator.reverseOrder()를 사용하면 내림차순으로 정렬합니다.
         *
         *    따라서 TreeSet<String> names = new TreeSet<>(Comparator.reverseOrder());는
         *    String 타입의 TreeSet을 생성하면서 내림차순으로 정렬하도록 설정하는 구문입니다.
         *    이렇게 설정하면 TreeSet에 요소가 추가될 때마다 내림차순으로 정렬되어 TreeSet에 저장됩니다.
         *    =================
         */

        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.nextLine();

        TreeSet<String> names = new TreeSet<>(Comparator.reverseOrder()); // 이름을 역순으로 정렬하는 TreeSet

        for (int i = 0; i < num; i++) {
            String strRaw = scanner.nextLine();
            String[] strList = strRaw.split(" ");
            String name = strList[0];
            String status = strList[1];

            if(status.equals("leave")
            ){
                names.remove(name);
            }else{
                names.add(name);
            }
        }

        for(String name : names)
            System.out.println(name);

        scanner.close();

    }
}