백준 - 수강신청

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/13414

[접근 방법]

단순하게 NM하면 무조건 시간 초과.

Hash 함수를 이용하여 다시 접근할 때 O(1)이어야 가능.

따라서 HashMap 사용함.

 

[Java 코드]

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int numOfStudentsEnrolled = Integer.parseInt(inputs[0]);
        int numOfStudent = Integer.parseInt(inputs[1]);
        Map<String,Integer> map = new HashMap<>();
        String[] students = new String[numOfStudent];

        int index = 0;
        for (int i = 0; i < numOfStudent; i++) {
            String studentNo = br.readLine();

            if (map.containsKey(studentNo)) {
                students[map.get(studentNo)] = null;
            }
            students[index] = studentNo;
            map.put(studentNo, index);
            index++;
        }

        index = 0;
        while (numOfStudentsEnrolled > 0 && index < numOfStudent) {
            if (students[index] != null) {
                System.out.println(students[index]);
                numOfStudentsEnrolled--;
            }
            index++;
        }
    }
}

[내 답안 수정하기]

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] inputs = br.readLine().split(" ");
        int numOfStudentsEnrolled = Integer.parseInt(inputs[0]);
        int numOfStudent = Integer.parseInt(inputs[1]);
        Map<String,Integer> map = new HashMap<>();
        String[] students = new String[numOfStudent];

        int index = 0;
        for (int i = 0; i < numOfStudent; i++) {
            String studentNo = br.readLine();
            students[index] = studentNo;
            if (map.containsKey(studentNo)) {
                students[map.get(studentNo)] = null;
            }
            map.put(studentNo, index);
            index++;
        }

        index = 0;
        while (numOfStudentsEnrolled > 0 && index < numOfStudent) {
            if (students[index] != null) {
                bw.write(students[index] + "\n");
                numOfStudentsEnrolled--;
            }
            index++;
        }
        bw.flush();
    }
}