[백준, BOJ 13414] 수강신청 (java)

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

메모리: 72,148 KB , 시간: 712 ms

사용 알고리즘: 자료 구조, 해시를 사용한 집합과 맵, 구현

728x90

---

수강신청을 한 순서대로 입력을 받으며

학번을 key 값으로 같은 학번이 나온 횟수를 value로 Map에 넣어준다.

 

다시 한번 수강신청을 한 순서대로 학번을 보며

map에서 학번에 해당하는 key값을 가진 value를 1씩 줄여준다.

만약 value가 이미 1이라면, 해당 학번이 마지막으로 수강신청 버튼을 누른 것이므로

답으로 출력해준다.

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

public class Main {

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        // key := 학번
        // value := key 학번이 몇 번 눌렀는지
        Map<String, Integer> map = new HashMap<>();

        // 대기열 순서
        Queue<String> q = new LinkedList<>();

        String id;
        for(int i = 0; i < L; i++) {
            id = br.readLine();
            map.put(id, map.getOrDefault(id, 0) + 1);
            q.add(id);
        }

        StringBuilder result = new StringBuilder();
        int count = 0; // 확정된 학생 수
        while(!q.isEmpty()) {
            id = q.poll();

            if(map.get(id) == 1) {
                result.append(id + "\n");
                if(++count == K) break;
            }
            else {
                map.put(id, map.get(id) - 1);
            }
        }

        System.out.print(result);
    }
}