백준 13414번 - 수강신청 (Java, 자바)

문제 링크

문제 설명

국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

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

위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목록의 길이 L(1 ≤ L ≤ 500,000)이 주어진다. 두 번째 줄부터 L개의 줄에는 수강신청을 버튼을 클릭한 학생의 학번이 클릭 순서대로 주어진다. 학번은 8자리의 숫자로 이루어져 있다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 수강신청 관리 시스템의 규칙을 적용한 후 수강신청에 성공한 인원의 학번을 한 줄에 1개씩 출력한다.

문제 풀이 방법

처음에 풀이했던 코드는 큐를 이용해서 풀이했다.
제일 먼저 들어온 학번이 수강신청 성공이 되므로 바로 큐를 떠올려서 큐를 이용해서 풀이 했지만 시간 초과가 떴다.

 

이문제의 핵심 포인트는 중복 데이터를 뒤로 보내는 것이다.
중복데이터를 다루는데는 HashSet만큼 좋은것은 없다고 생각이 들었다.
하지만 HashSet은 순서가 없는 자료구조이다.

 

HashSet기능을 하면서 순서가 있는 자료구조인 LinkedHashSet을 이용하면 매우 쉽게 풀이 할수 있다.

 

LinkedHashSet 에 값이 있다면 remove 를 통해 해당 값을 제거한 뒤 다시 add 를 통해서 값을 넣어 주면 된다.

마지막에 출력할 갯수만큼만 출력하면 클리어!

전체 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        String[] A = new String[n];

        for (int i = 0; i < n; i++) {
            A[i] = br.readLine();
        }

        LinkedHashSet<String> set = new LinkedHashSet<>();
        for(String item : A){
            if(set.contains(item)){
                set.remove(item);
            }
            set.add(item);
        }

        int temp = 0;

        for(String answer : set){
            temp++;
            System.out.println(answer);
            if(temp == k) break;
        }
    }
}