13414번: 수강신청(Java)

 

 

 학번을 저장하면서 만약 이미 저장하고 있는 학번이라면(한번 더 클릭했다면) 삭제하고 다시 저장하면 순서의 맨 뒤로 저장된다. 

 

 

 

 

 LinkedList를 써서 풀었더니 시간초과가 생겼다. 구글링을 해 보니 LinkedList의 add, remove 연산의 시간복잡도가 O(n)이라는 것이 원인이라는 결론이 나왔다. for문을 사용하며 입력을 받음과 동시에 add, remove를 하니 시간복잡도가 O(n^2) 이 되는 것이었다.

 그래서 LinkedHashSet을 사용했다. 기존의 Set은 순서를 보장하지 않지만, LinkedHashSet은 순서를 보장하므로 클릭 순서에 따라 저장할 수 있다.

 

입력이 많으므로 BufferedReader를 사용했다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int limit = Integer.parseInt(st.nextToken());
int student = Integer.parseInt(st.nextToken());
LinkedHashSet<String> list = new LinkedHashSet<>();

for(int i = 0; i<student; i++)
{
    String s = br.readLine();
    if(list.contains(s))
    {
        list.remove(s);
    }
    list.add(s);
}

 

이렇게 하면 문제에서 수강신청자들의 순서를 정하는 규칙을 만족한다.

 

 

 

마지막으로 가능 인원만큼 출력하면 된다.

 

 

 

 

 

 

 

결과 코드

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 limit = Integer.parseInt(st.nextToken());
        int student = Integer.parseInt(st.nextToken());
        LinkedHashSet<String> list = new LinkedHashSet<>();

        for(int i = 0; i<student; i++)
        {
            String s = br.readLine();
            if(list.contains(s))
            {
                list.remove(s);
            }
            list.add(s);
        }

        for(Object s : list.toArray())
        {
            if(limit > 0)
            {
                System.out.println(s);
                limit--;
            }

        }
    }
}