[백준] 13414번 수강신청

문제는 다음과 같다.

백준 13414 수강신청
구현이 어렵진 않았지만, 시간복잡도와 메모리를 신경써야 했던 문제다. 처음엔 문제에서 나온 과정을 따라 2중 for 문을 활용했지만, 시간 초과로 틀렸다. 시간 복잡도를 O(n^2) 보다 줄여야 했다. 두 번째 방법으로는 스택을 2개 만들고 마지막 데이터부터 탐색하고 HashSet을 활용해 O(N)의 복잡도로 문제를 풀어 냈지만 이 또한 메모리를 너무 많이 소비하게 되었다.

LinkedHashSet의 활용

LinkedHashSet은 HashSet과 매우 유사하지만 '순서를 고려하는가'에서 차이가 있었다. LinkedHashSet과 HashSet은 contains() 메소드를 사용할 때의 시간 복잡도가 O(1)로 중복을 확인할 때 유용하게 사용할 수 있다. 또한 remove() 메소드를 활용할 때도 해당 element가 없다면 false를 리턴할 뿐 에러가 나지 않으므로 활용하기 좋다. 이 문제와 같은 경우 순서를 고려해야 하기 때문에 LinkedHashSet를 활용하면 쉽게 풀 수 있었다.

public class Main {

    public static void main(String[] args) {
        try {
            int capacity, n;
            String tmp;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st = new StringTokenizer(br.readLine());
            capacity = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            LinkedHashSet<String> lhs = new LinkedHashSet<>();  
            for (int j = 0; j < n; j++) {
                tmp = br.readLine();
                lhs.remove(tmp);    // 포함되어 있지 않더라도 에러를 내지 않는다
                lhs.add(tmp);
            }
            Iterator<String> iter = lhs.iterator(); // LinkedHashSet은 인덱스 하나하나 꺼내볼 수 없다.
            for (int j = 0; iter.hasNext() && j < capacity ; j++) {
                bw.write(iter.next());
                bw.write("\n");
            }
            bw.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}```