[백준] 10815 : 숫자 카드 (List와 Set의 Contains()) - JAVA

백준 단계별 문제풀이 14단계 (집합과 맵)

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

10815번: 숫자 카드

 

 

# 문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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보다 작거나 같다

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

 

출력

1 0 0 1 1 0 0 1

 

# 필요개념

문제를 보고 한 생각은 상근이가 가지고 있는 수를 리스트에 넣어 contains() 메소드를 사용하는 것이었다. 그래서 실행해보았는데 시간초과가 떴다. (요즘 부쩍 시간초과가 많이 뜬다 ㅎ..)

contains 메소드를 제외하고는 for문을 쓴 거밖에 없는데 이게 원인은 아닐 거 같아 contains 메소드를 찾아보았다.

 

그 결과 List와 Set의 시간복잡도가 각각 O(n)과 O(1)이었다. 그래서 Set을 사용해 풀어봤는데 성공했다. 같은 contains인데 무슨 차이점이 있길래 시간복잡도 차이가 이렇게나 크게 나는 것일까?

(추가로 Map의 containsKey() 메소드 또한 O(1)이다.)

 

✅ List _ O(n)

• ArrayList는 중복을 허용하고 순서를 보장한다. contains 메소드를 실행하면 처음부터 순차적으로 탐색한다.
• LinkedList는 노드끼리 연결해서 내부 객체를 관리한다. 

ArrayList와 LinkedList를 비교하면 ArrayList가 더 빠르다!

 

✅ Set _ O(1)

• HashSet은 비선형구조라 순서가 없고 인덱스도 없다. 또 중복을 자동으로 제거한다 (중복허용X) 
  그래서 모든 데이터를 찾을 필요 없이 바로 찾아낼 수 있다.

순서가 중요하거나 중복이 있으면 List를, 중복이 없을 땐 Set을 사용하는 게 더 효율적이다!

 

# Code

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        HashSet<Integer> haveElement = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < m ; i++) {
            haveElement.add(Integer.valueOf(st.nextToken()));
        }
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int j = 0 ; j < n ; j++) {
            int a = Integer.parseInt(st1.nextToken());
            if (haveElement.contains(a)) sb.append(1).append(" ");
            else sb.append(0).append(" ");
        }
        System.out.println(sb);
    }
}

 

# 결과