[JAVA] 백준 13414번 【S3.수강신청】

문제

13414번: 수강신청

---

풀이

먼저 이 문제는, 수강 신청을 한 학생들을 순서대로 자료구조에 넣어야 하는데,

 

이미 그 자료구조에 들어가 있는 학생인 경우, 제일 뒷 순서로 다시 집어넣어야 한다.

 

이 아이디어는, 이 문제를 푸는 누구나 떠올렸을텐데

 

생각보다 간단하게 풀릴 줄 알았는데 아니었다.

 

 

1️⃣ map과 priority queue 사용

set을 이용해서 중복여부를 확인할 수 있지만, 수강 신청 순서를 확인할 순 없다.

 

		HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < L; i++) {
            String id = br.readLine();
            if (map.containsKey(id)) {
                map.remove(id);
                map.put(id, i);
            } else {
                map.put(id, i);
            }
        }

 

따라서, map을 이용해서 수강 신청 순서 정보까지 함께 넣을 수 있다.

 

그렇게, map에 이미 수강 신청 이력이 있는 학생의 경우 삭제하고 다시 입력해주면 된다.

 

map에 순서 정보를 넣었지만, 정렬은 따로 불가능 하므로

 

map에 입력된 순서에 따라 정렬하기 위해, map에 있는 원소들을 순차적으로 우선 순위 큐에 넣었다.

 

단, 우선순위 큐에 집어넣을 때 새로운 클래스를 정의해서 정렬 조건과 함께 구현하면 된다.

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int K = Integer.parseInt(input[0]), L = Integer.parseInt(input[1]);
        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < L; i++) {
            String id = br.readLine();
            if (map.containsKey(id)) {
                map.remove(id);
                map.put(id, i);
            } else {
                map.put(id, i);
            }
        }

        PriorityQueue<Student> pq = new PriorityQueue<>((a, b) -> a.idx - b.idx);
        for (String s : map.keySet()) {
            pq.offer(new Student(s, map.get(s)));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < K; i++) {
            if (!pq.isEmpty()) {
                sb.append(pq.poll().id + "\n");
            }
        }
        System.out.println(sb);
    }

    static class Student {
        String id;
        int idx;

        public Student(String id, int idx) {
            this.id = id;
            this.idx = idx;
        }
    }
}

 

결과

 

2️⃣ LinkedHashSet 사용

이 문제를 더 쉽게 풀 수 있는 방법이 없나 찾아보다가 처음 알게된 자료구조이다.

 

set인데, 순서를 보장해주는 set이라고 한다.

 

따라서, 이 자료구조를 알고 있었다면 정~~말로 쉽게 이 문제를 해결할 수 있다.

 

import java.io.*;
import java.util.*;

public class Main2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int K = Integer.parseInt(input[0]), L = Integer.parseInt(input[1]);
        LinkedHashSet<String> set = new LinkedHashSet<>();

        for (int i = 0; i < L; i++) {
            String id = br.readLine();
            if (set.contains(id)) {
                set.remove(id);
                set.add(id);
            } else {
                set.add(id);
            }

        }

        StringBuilder sb = new StringBuilder();
        for (String id : set) {
            sb.append(id + "\n");
            if (--K == 0) {
                break;
            }
        }
        System.out.println(sb);
    }

}

 

결과

1번 방법 보다 따른 시간으로 통과하였다.