백준 10815 - 숫자 카드
Updated:
Java
10815 번 - 숫자 카드
문제
접근 방법
java의 collection의 HashSet
과 이분탐색으로 해결하였다.
-
Set 사용
HashSet
에 숫자 카드 데이터를 넣은 후, 확인하는 숫자를set.contains()
메서드로 확인한다.
HashSet
의contains()
메서드의 시간 복잡도는O(1)
으로 시간 복잡도 내에 해결 가능하다. -
이분 탐색 사용
카드 데이터를 배열에 담은 후 오름 차순으로 정렬을 한다.
이후 확인할 숫자를 이분 탐색 메서드의 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);
}
}