intro : 자료구조를 많이 알면 알수록 문제풀이는 쉬워진다. 또한 시간 복잡도의 계산능력이 좋아지는거 같다.

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 “enter”나 “leave”가 주어진다. “enter”인 경우는 출근, “leave”인 경우는 퇴근이다. 회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

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

문제 풀이1 (잘못된 풀이 - 런타임 에러 (ConcurrentModification))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Map<String, String> map = new HashMap<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int forCount = Integer.parseInt(br.readLine());
        for (int i = 0; i < forCount; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            map.put(st.nextToken(), st.nextToken());
        }

        for (String key : map.keySet()) {
            String status = map.get(key);
            if (!status.equals("enter")) {
                map.remove(key);
            }
        }
 
        TreeSet<String> treeSet = new TreeSet<>(map.keySet());
        Iterator<String> iterator = treeSet.descendingIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

문제 풀이2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<String> set = new HashSet<>();
        int forCount = Integer.parseInt(br.readLine());
        for (int i = 0; i < forCount; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            String status = st.nextToken();
            if (status.equals("enter")) {
                set.add(name);
            } else {
                set.remove(name);
            }
        }

        StringBuilder sb = new StringBuilder();
        TreeSet<String> sortSet = new TreeSet<>(set);
        Iterator<String> iterator = sortSet.descendingIterator();
        while (iterator.hasNext()) {
            sb.append(iterator.next());
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

문제해석

문제를 보고 떠오른 아이디어는, 입출입 값을 map이나 set을 통해 관리하고 leave를 한 인원은 제외한다음, Collection 끼리의 타입 변환은 가능하기에 정렬 기능을 제공하는 자료구조인 TreeSet으로 변환 후, 역순으로 값을 출력하자가 생각이었다. (list로도 변환할수 있고, list의 역순 출력도 고려해 보았다.)

이때 자료구조는 map이 더 나아보여서 map으로 문제를 풀어보았는데, remove를 하는 시점에서 Concurrent Modification Exception이 발생하였으며, map에서는 순회하면서 remove를 하는게 예외를 발생시킨다는 점을 인지하게 되었다. 다만 set은 map과 내부 구조가 달라, 순회하면서 remove를 하여도 예외가 발생하지 않아 문제풀이 2번 방식으로 문제를 풀 수 있다는것이 포인트가 될 수 있다.

또한 시간적으로 단축시켜야 하기에 병목현상이 발생할수 있는 System.out.println을 반복문에서 사용하지않고, StringBuilder를 통해 문자열을 구성한 후, 한번에 출력하는 형식으로 로직을 구성하였다. StringBuilder를 사용하기전에는 1초가 걸리는 로직이, 후에 0.5초로 엄청난 속도 개선이 이루어 졌다.

I am visible

contact

문제

입력

출력

문제 풀이1 (잘못된 풀이 - 런타임 에러 (ConcurrentModification))

문제 풀이2

문제해석