🔥[99클럽 코테 스터디] 13일차 TIL - 숫자 카드

⏳문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

입출력 예

예제 입력 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

---

✏️풀이

첫 번째 시도

import java.util.*;

public class Baekjoon_10815 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> N_list = new ArrayList<>();
        ArrayList<Integer> M_list = new ArrayList<>();
        
        // 상근이의 카드 입력
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            N_list.add(sc.nextInt());
        }
		
        // 비교할 카드 입력
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            M_list.add(sc.nextInt());
        }

		// 상근이의 카드에 존재하는 지 하나씩 확인
        for (int i = 0; i < M; i++) {
            if (N_list.contains(M_list.get(i))) {
                System.out.print(1 + " ");
            }
            else {
                System.out.print(0 + " ");
            }
        }
        System.out.print("\b"); // 마지막 공백 제거
        

        sc.close();
    }
}

나는 단순히 비교할 카드와 상근이의 카드를 비교하기만 하면 된다고 생각해, 두 개의 ArrayList를 만들어서 contains함수를 통해 해당 카드가 상근이의 카드를 담고 있는 ArrayList에 존재하는 지 여부를 판별하도록 구현하였다.

출력 결과는 동일했으나, 결과는 시간 초과로 인해 실패였다.

두 번째 시도

그렇다면 시간을 단축시킬 수 있는 방법에는 무엇이 있을까 가만히 생각해 보았다.

원인이 뭔가 ArrayList의 contains()메서드 일 것이라는 생각이 들었다.

그래서 검색을 해보니, ArrayList에서 contains()메서드를 사용하면, 리스트의 모든 요소를 순회하면서 특정 요소가 존재하는 지 확인하는 과정을 거치기 때문에, 최악의 경우 $O(N)$의 시간이 소요 된다는 사실을 깨달았다.

게다가 이걸 M만큼 반복하도록 코드를 구성해 놓았으니, $O(N * M)$이라는 비효율적인 실행 시간을 초래했던 것이다.

💻최종 코드

그래서 나는 ArrayList대신 Set을 사용해 문제를 다시 풀었다.
Set 중에서도 Hash Set은 Hash table을 기반으로 작동하는 Set이기 때문에, 검색하는 작업을 수행하는 데 상수 시간밖에 소요되지 않는다는 장점이 있다!

import java.util.*;

public class Baekjoon_10815 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> N_set = new HashSet<>(); // Hash Set
        StringBuilder result = new StringBuilder();
        
        // 상근이의 카드 입력
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            N_set.add(sc.nextInt());
        }

		// 비교할 카드 입력
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            if (N_set.contains(sc.nextInt())) {
                result.append(1).append(" ");
            }
            else {
                result.append(0).append(" ");
            }
        }
        result.toString().trim(); // 마지막 공백 제거
        System.out.print(result);
        
        sc.close();
    }
}

이렇게 ArrayList대신 Hash Set을 사용함으로써 실행 시간을 단축시킬 수 있었다!

---

🔗문제 링크
💻Repository