📌 문제

[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보다 작거나 같다.

⬆️ 출력

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

💡 코드

⏱️ 분명 집합과 맵 단계이긴 한데,, 어떻게 접근해야할지 감이 안와서 혹시나 하는 마음으로 배열 2개 만든 다음에 이중 for문 돌려서 풀어봤지만 역시나 시간 초과,,

import java.io.*;
import java.util.*;
public 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));

		int n = Integer.parseInt(br.readLine());
		int[] arr1 = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr1[i] = Integer.parseInt(st.nextToken());
		}
		
		int m = Integer.parseInt(br.readLine());
		int[] arr2 = new int[m];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<x;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(j == n-1) {
					sb.append(0 + " ");
				}
				
				if(arr2[i] == arr1[j]) {
					sb.append(1 + " "); break;
				}
			}
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

✅ 얼마 전에 컬렉션 프레임워크에 대해 정리한 글을 작성한 것이 생각이 났고, 이를 보니 add() 메서드가 단순히 객체에 요소를 저장할 뿐만 아니라 저장 여부를 boolean 타입으로 리턴한다는 것이 기억났다! Set 계열은 중복 데이터를 허용하지 않으므로, add() 메서드를 통해 중복 데이터를 저장하려고 하면 false를 리턴하며 값을 저장하지 않는다. 우리가 일반적으로 add()를 통해 값을 저장하는 프로세스에서는 true를 리턴한다.

이를 활용하여 add() 메서드가 true값을 리턴하면 값이 중복되지 않고 제대로 저장되었다, 즉, 상근이가 해당 카드를 가지고 있지 않다는 뜻이므로 0을 출력하고, false를 리턴하면 가지고 있던 카드와 값이 중복되어 저장되지 않았다는 뜻이므로 1을 출력한다.

import java.io.*;
import java.util.*;
public 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));

		int n = Integer.parseInt(br.readLine());
		Set<Integer> set = new HashSet<>();
		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());
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<m;i++) {
			if(set.add(Integer.parseInt(st.nextToken()))) 
				sb.append(0 + " ");
			else sb.append(1 + " "); 
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

➕ 나는 단계별로 문제를 풀다 보니 이번 단계가 집합과 맵 단계라서 Set을 쓰는 쪽으로 접근했는데, 다른 사람의 풀이를 보니 이분 탐색을 활용하는 코드가 훨씬 많았다! 이분(이진) 탐색이란 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘이다. 확실히 이분 탐색을 활용하면 이중 for문을 사용한 첫 코드의 시간 문제를 해결할 수 있을 것 같아서 이분 탐색으로도 풀어봤다!

✅ 상근이가 가지고 있는 카드의 숫자들을 arr1[], m개의 카드의 숫자들을 arr2[]에 저장하고, 이진 탐색을 통해 arr2[]의 숫자들이 arr1[]에 존재하는지 탐색한다. 이 때, arr1[]은 오름차순 정렬된 상태여야 한다!

메서드 binarySearch(int[], int)는 이진 탐색을 수행한다. 검색 시작 인덱스 start와 끝 인덱스 end를 선언하고, 해당 범위의 절반 인덱스 idx에 해당하는 요소의 값 arr[idx]와 찾아야 하는 값 x를 비교하여 일치하면 해당 카드가 있다는 뜻이므로 1을 반환하고, arr[idx] 값이 크다면 범위가 더 작은 값으로 이동해야 하므로 끝 인덱스를 절반 인덱스 앞쪽(idx -1)으로 이동시켜야 한다. 반대로 arr[idx] 값이 작다면 범위가 더 큰 쪽으로 이동해야 하므로 시작 인덱스를 절반 인덱스 뒤쪽(idx + 1)으로 이동시켜야 한다.

import java.io.*;
import java.util.*;
public class Main {
	
	static int binarySearch(int[] arr, int x) {
		int start = 0; // 시작 인덱스
		int end = arr.length - 1; // 끝 인덱스
		
		while(start <= end) {
			int idx = (start + end) / 2;
			if(arr[idx] == x) return 1; // 검색 성공 : 값 존재
			else if(arr[idx] > x) end = idx - 1;
			else start = idx + 1;
		}
		
		return 0; // 검색 실패 : 값 없음
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr1 = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr1[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr1); // 이진 검색을 위해 정렬 수행
		
		int m = Integer.parseInt(br.readLine());
		int[] arr2 = new int[m];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<m;i++) {
			sb.append(binarySearch(arr1, arr2[i]) + " ");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

Set을 사용하면 시간은 적게 걸리지만 메모리를 많이 먹고, 이분 탐색을 사용하면 메모리는 적게 먹지만 시간은 좀 더 오래걸린다. 각자의 장단점이 확실한듯,,!