[백준] 13414번 : 수강신청 – JAVA [자바]

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

13414번: 수강신청

 

---

• 문제

 

 

---

• 문제 풀이

백준 13414번 수강신청은 실버 3 난이도의 구현 및 해시 문제이다. 이 문제에서는 과목의 수강 가능 인원 K명과 대기목록의 길이 L이 주어진다. 그리고 L개 줄의 학생 번호가 주어진다. 이때 수강신청을 성공한 학생들을 출력하면 된다. 

 

수강 신청 시스템은 다음과 같다.

 

1. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
2. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
3. 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

이 문제는 해시맵을 이용해서 풀 수 있다. 우선, 키가 String, 그리고 값이 Integer 형인 해시맵을 만든다. 이 String은 학생 ID를 저장하고 값인 Integer는 대기 목록에 있는 순서를 저장한다. 

 

해시맵을 이용한 이유는 바로 두 번째 룰인 대기열에 있는 상태에서 수강신청을 하면 대기목록의 맨 뒤로 밀려난다는 룰 때문이다. 왜냐하면, 해시맵은 키가 같은 객체를 저장하지 않기 때문이다. 

 

이 문제를 풀기 위해서는 대기목록을 입력받을 때 이 학생들을 순서대로 해시맵에 넣어주는 것이다. 그리고, 중복된 학생이 있으면 해시맵에 있는 객체를 override 시키기 때문이다. 

 

대기목록에 있는 학생들을 해시맵에 저장시킨 후 이 학번을 대기 순서에 따라 배열에 저장시켜 준다.

 

해시맵을 순회하는 방법 중에 하나는 entrySet() 함수를 이용하는 것이다. 이 함수를 이용하면 키와 값을 둘 다 구할 수 있다. 따라서, 크기가 L인 배열을 만들고 이 해시맵에 저장되어 있는 값들을 인덱스로 삼아서 학번들을 이 배열에 저장시켜 준다. 그리고, 배열 처음부터 K개의 학번들을 출력해 주면 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 수강 가능 인원(K)과 대기목록의 길이(L)를 입력 받음
        int k = Integer.parseInt(st.nextToken()); // 수강 가능 인원
        int l = Integer.parseInt(st.nextToken()); // 대기목록의 길이

        // 학번을 대기목록의 순서와 매핑하여 저장하는 HashMap
        Map<String, Integer> map = new HashMap<>();

        // 대기목록을 순회하며 학번과 대기순서를 HashMap에 저장
        for (int i = 0; i < l; i++) {
            String s = br.readLine(); // 학번 입력
            map.put(s, i); // 학번을 key로, 대기순서(i)를 value로 HashMap에 저장
        }

        // 학번을 대기순서에 따라 배열에 저장
        String[] arr = new String[l];
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            arr[entry.getValue()] = entry.getKey();
        }

        // 최종 수강신청에 성공한 학생들의 학번을 저장하는 StringBuilder
        StringBuilder sb = new StringBuilder();

        // 배열을 순회하며 수강신청에 성공한 학생들의 학번을 StringBuilder에 추가
        for (int i = 0; i < l; i++) {
            if (arr[i] != null) {
                sb.append(arr[i] + "\n");
                k--; // 수강 가능 인원을 하나씩 감소시킴
            }
            if (k == 0) break; // 수강 가능 인원이 0이 되면 더 이상 수강신청 진행하지 않음
        }

        // 최종적으로 수강신청에 성공한 학생들의 학번을 출력
        System.out.println(sb);
    }
}