[백준] 13414 수강신청 - LinkedHashSet(해시셋) JAVA

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

13414번: 수강신청

코드설명

LinkedHashSet 을 활용합니다.

 

물론, ArrayList나 LinkedList를 만들어서 직접 순서를 바로바로 뒤로 바꿔주는것도 가능합니다.

하지만, 갱신하려는 학번의 위치를 매번 탐색할경우 최악의 경우 O(N^2)의 복잡도가 나옵니다.

 

그대신에 LinkedHashSet을 활용해서 조회에 걸리는 시간을 O(1)로 조회할 수 있습니다.

코드

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, T;
	public static HashSet<String> hashset = new LinkedHashSet<String>();
	public static int answer = 0;
	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());
		
		for(int i=0;i<L;i++) {
			st = new StringTokenizer(br.readLine());
			String input = st.nextToken();
			if(hashset.contains(input) == true) {
				hashset.remove(input);
			}
			hashset.add(input);
		}
		
		answer = 0; 
		for(String input : hashset) {
			if(answer < K) {
				System.out.println(input);
				answer += 1;
			}
		}
	}
}

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;
 
public class Main {
    private static int N, T, K, M, L;
    private static int[] arr;
    private static int answer = 0;
    private static LinkedHashSet<String> hashset = new LinkedHashSet<>();
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		
		for(int i=0;i<L;i++) {
			st = new StringTokenizer(br.readLine());
			String sNum = st.nextToken();
			if(hashset.contains(sNum) == true) {
				hashset.remove(sNum);
			}
			hashset.add(sNum);
		}
		
		for(String v : hashset) {
			if(++answer > N) break; 
			System.out.println(v);
		}
    }
    
    
}