백준 10815 - 숫자 카드

Java

10815 번 - 숫자 카드

문제

접근 방법

java의 collection의 HashSet과 이분탐색으로 해결하였다.

1. Set 사용
   HashSet에 숫자 카드 데이터를 넣은 후, 확인하는 숫자를 set.contains()메서드로 확인한다.
   HashSet의 contains()메서드의 시간 복잡도는 O(1)으로 시간 복잡도 내에 해결 가능하다.

2. 이분 탐색 사용
   카드 데이터를 배열에 담은 후 오름 차순으로 정렬을 한다.
   이후 확인할 숫자를 이분 탐색 메서드의 target으로 두어 탐색한다.
   이분 탐색의 시간 복잡도는 O(logN)이다.

코드 - Set 사용

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

public class Main {
	static int n, result, m;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	Set<Integer> card = new HashSet<>();

    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		card.add(stoi(stk.nextToken()));		// 카드 삽입
    	}

    	StringBuilder sb = new StringBuilder();
    	m = stoi(br.readLine());
    	stk = new StringTokenizer(br.readLine());
    	int curN;
		// 카드 탐색
    	for(int i = 0; i < m; i++) {
    		curN = stoi(stk.nextToken());
			// 카드에 존재하는지 확인
    		if(card.contains(curN)) {
    			sb.append(1).append(" ");
    		}
    		else {
    			sb.append(0).append(" ");
    		}
    	}

    	System.out.println(sb.toString());
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

코드 - 이분 탐색 사용

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

public class Main {
	static int n, result, m;
	static int[] card;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	card = new int[n];
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		card[i] = stoi(stk.nextToken());
    	}

    	StringBuilder sb = new StringBuilder();
    	m = stoi(br.readLine());
    	stk = new StringTokenizer(br.readLine());
    	int curN;
    	Arrays.sort(card);
    	for(int i = 0; i < m; i++) {
    		curN = stoi(stk.nextToken());
    		sb.append(binarySearch(0,n - 1, curN)).append(" ");
    	}

    	System.out.println(sb.toString());
    	br.close();
	}
	// 카드들을 이분 탐색
	static int binarySearch(int low, int high, int target) {

		int mid;
		if(low <= high) {

			mid = (low + high) / 2;
			// 중간 카드가 목표랑 같으면
			if(card[mid] == target) {
				return 1;
			}
			// 목표보다 중간 카드가 클 시
			else if(target < card[mid]) {
				return binarySearch(low, mid - 1, target);
			}
			// 목표보다 중간 카드가 작을 시
			else {
				return binarySearch(mid + 1, high, target);
			}

		}

		return 0;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}