[JAVA] 백준 10815 숫자카드_집합과맵

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

10815번: 숫자 카드

 

접근 :

 

- 내가 보유할 카드수 N 을 입력 받음

 

- N 장의 카드에 해당하는 숫자들을 받음

 

- 비교할 대상 의 숫자수 M 을 입력 받음

 

- M 개의  해당하는 숫자들을 받음

 

- 수 로만 이루어져 있으므로 이진 탐색 방법을 사용

 

- 이진 탐색을 사용하기 위해 N을 오름차순으로 정렬

 

- 입력 받은 M 을 한 개씩 꺼내어 N장의 카드들에 있는 수 인지 판별

 

 

코드 구현: 

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// n 입력
		int n = Integer.parseInt(br.readLine());
		String[] inputs = br.readLine().split(" ");
		int[] n_array = new int[n];
		
		// n 카드에 해당하는 숫자들 입력
		for (int i = 0; i < n; i++) n_array[i] = Integer.parseInt(inputs[i]);

		// 오름차순 정렬
		Arrays.sort(n_array);
		
		// m 입력
		int m = Integer.parseInt(br.readLine());
		inputs = br.readLine().split(" ");

		int number = 0;
		int low = 0;
		int high = n - 1;
		int mid;
		boolean is_contain = false;

		for (int j = 0; j < m; j++) {
			low = 0;
			high = n - 1;
			
			//m 으로 입력 받은 숫자를 순차적으로 꺼냄
			number = Integer.parseInt(inputs[j]);
			is_contain = false;
			
			//2진 탐색
			while (low <= high) {
				mid = (low + high) / 2;

				// 탐색 중 일치하는 수를 발견한 경우
				if (number == n_array[mid]) {
					sb.append(1).append(" ");
					is_contain = true;
					break;
				} else if (number < n_array[mid]) {
					high = mid - 1;
				} else {
					low = mid + 1;
				}
			}

			// 탐색 후 찾는 수가 없는 경우
			if (!is_contain) sb.append(0).append(" ");
		}
		System.out.println(sb);
		br.close();
	}
}

 

* 번외 :

 

- 위의 코드를 map으로 수정 후 성능 비교

 

- 가독성 및 성능이 향상됨

 

-map을 사용한 코드

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		// n 입력
		int n = Integer.parseInt(br.readLine());
		String[] inputs = br.readLine().split(" ");

		HashMap<String, Integer> numbers = new HashMap<>();

		// n 카드에 해당하는 숫자들 입력
		for (int i = 0; i < n; i++) {
				numbers.put(inputs[i], 1);
		}

		// m 입력
		int m = Integer.parseInt(br.readLine());
		inputs = br.readLine().split(" ");

		for (int j = 0; j < m; j++) {

			if (numbers.containsKey(inputs[j])) {
				//sb.append(numbers.get(inputs[j])).append(" ");
				sb.append(1).append(" ");
			} else {
				sb.append(0).append(" ");
			}
		}
		System.out.println(sb);
		br.close();
	}
}