[백준] 10815. 숫자 카드 (Java)

 

🔒 문제

10815번: 숫자 카드

 

🔑 알고리즘

해시셋(HashSet)

 

💡  풀이

숫자 카드에 적혀있는 값을 인덱스로 Set에 저장하여 카드를 가지고 있는지 아닌지 여부를 판단한다.

 

숫자 카드에 적혀있는 수가 -10,000,000 에서 10,000,000 로 약 2천만이지만

숫자 카드의 개수는 최대 500,000 이므로 

O(20,000,000 + 1)의 공간 복잡도를 가지는 배열보다

O(500,000) 의 공간 복잡도를 가지는 셋을 사용하는 것이 효율적이다.

 

숫자 카드에 적힌 값을 셋에 추가하고

입력으로 들어온 값이 셋에 있다면 1, 아니면 0을 출력한다.

 

 

* String은 불변(immutable) 객체이기 때문에 + 연산을 수행할 때 새로운 String 객체를 만든다.

M이 최대 500,000 이므로 500,000 번의 + 연산이 이루어지면 그만큼 새로운 객체를 만들고 시간초과가 날 수 있다.

따라서 mutable한 StringBuilder를 이용해 연산을 한 후 이를 출력한다.

 

* 이분 탐색으로도 풀 수 있는데 

이분 탐색의 경우 정렬 후 최대 M개의 원소를 0~N의 범위로 이분 탐색하므로

시간 복잡도는 O(NlogN + MlogN) = O( (M+N)logN ) 일 것이고

 

셋을 이용한 풀이는 N번만큼 셋에 삽입 + M번만큼 검색(O(1)) 으로 시간 복잡도는 O(M+N)일 것이다.

 

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Set<Integer> set = new HashSet<>();

		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			set.add(Integer.parseInt(st.nextToken()));

		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; i++) {

			if (set.contains(Integer.parseInt(st.nextToken())))
				sb.append("1 ");
			else
				sb.append("0 ");
		}

		System.out.println(sb);
	}
}