[ 백준 13414번 JAVA ] 수강신청

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

 

 

처음엔 linkedlist를 사용해서 풀었다. 

그러나 linkedlist를 사용하면 add,remove 연산의 시간복잡도가 O(n)이라고 한다. 

for문을 사용하여 입력을 받음과 동시에 add,remove를 사용하면 시간복잡도는 O(n^2)이 된다. 

따라서 LinkedHashSet을 사용했다. 

기존의 hashset 은 순서를 보장하지 않지만, LinkedHashSet은 순서를 보장한다. 

 

Solution

package SILVER;

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

public class bj13414 {
    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 L = Integer.parseInt(st.nextToken());

        LinkedHashSet<String> set = new LinkedHashSet<>();

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

        int cnt=0;
        for(String num : set){
            System.out.println(num);
            cnt++;
            if(cnt==K) break;
        }
    }
}