https://www.acmicpc.net/problem/13414
13414번: 수강신청
입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목
www.acmicpc.net
코드설명
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);
}
}
}