[BOJ-Silver3] 13414번 수강신청

🚨 첫번째 풀이 - 시간초과

✔️ ArrayList

• arrayList에 넣기 -> 해당 학번이 arrayList에 있으면 인덱스 번호 찾고 삭제 후 넣기
• contains, indexOf, remove 모두 O(n)으로 시간초과 발생 !!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

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 l = Integer.parseInt(st.nextToken());

		ArrayList<String> students = new ArrayList<>();
		for(int i = 0; i<l; i++){
			String input = br.readLine();
            // arrayList에 있으면 인덱스 찾아서 삭제
			if (students.contains(input)){
				int idx = students.indexOf(input);
				students.remove(idx);
			}
			students.add(input);
		}

		for(int i = 0; i<k ;i++){
			System.out.println(students.get(i));
		}
	}
}

💡 두번째 풀이

✔️ Queue + HashMap

• queue에 학번 넣어서 순서 저장
• hashMap에 학번 넣고 해당 학번이 없으면 1로 있으면 +1로 개수 저장
• queue에서 하나씩 꺼내서 해당 학번의 value가 1을 넘으면 -1로 개수 줄이기
• value가 1이면 하나만 있으므로 그대로 출력
• 출력할때마다 k를 -1하고 0이면 종료

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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 l = Integer.parseInt(st.nextToken());

		HashMap<String, Integer> hm = new HashMap<>(); // 학번 개수 저장
		Queue<String> q = new LinkedList<>(); // 학번 순서 저장
        // queue와 hashmap에 넣기
		for(int i = 0; i<l; i++){
			String input = br.readLine();
            // hashmap에 없으면 1, 있으면 +1
			hm.put(input, hm.getOrDefault(input, 0) + 1);
			q.add(input);
		}

		while(!q.isEmpty()){
			String curr = q.poll();
            // 큐에서 꺼낸 학번의 value가 1를 넘으면 -1 해주기
			if (hm.get(curr) > 1){
				hm.put(curr, hm.getOrDefault(curr, 0) - 1);
			} else { // 학번의 value가 1이면 출력
				System.out.println(curr);
				k--;
			}

			// k개 출력하기
			if (k==0)
				break;
		}
	}
}

💡 세번째 풀이

✔️ LinkedHashSet

• 다른 사람 풀이 참고
• LinkedHashSet -> 순서 있는 HashSet
• Hash 이므로 contains, remove가 모두 O(1)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

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 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);
		}

		for(String s : set){
			System.out.println(s);
			k--;
			if(k == 0) break;
		}
	}
}