https://www.acmicpc.net/problem/1920
import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int nNum = sc.nextInt();
ArrayList<Integer> nList = new ArrayList<>();
for(int i = 0; i< nNum; i++) {
nList.add(sc.nextInt());
}
int mNum = sc.nextInt();
int[] mList = new int[mNum];
for(int i = 0; i< mNum; i++) {
mList[i] = sc.nextInt();
}
for(int i = 0; i< mNum; i++) {
if (nList.contains(mList[i]))
System.out.println(1);
else System.out.println(0);
}
}
}
import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int nNum = sc.nextInt();
int[] nList = new int[nNum];
for(int i = 0; i< nNum; i++) {
nList[i] = sc.nextInt();
}
Arrays.sort(nList);
int mNum = sc.nextInt();
int[] mList = new int[mNum];
for(int i = 0; i< mNum; i++) {
mList[i] = sc.nextInt();
}
for(int i = 0; i< mNum; i++) {
System.out.println(binarySearch(nList, mList[i]));
}
}
public static int binarySearch(int[] nList, int searchNum) {
int start = 0;
int end = nList.length-1;
int cursor = (start+end)/2;
while (start <= end) {
if (nList[cursor] == searchNum) return 1;
else if (nList[cursor] < searchNum) {
start = cursor+1;
}
else if (nList[cursor] > searchNum) {
end = cursor-1;
}
cursor = (start+end)/2;
}
return 0;
}
}
import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
HashSet<Integer> set = new HashSet<>();
int nNum = sc.nextInt();
for(int i = 0; i< nNum; i++) {
set.add(sc.nextInt());
}
int mNum = sc.nextInt();
int[] mList = new int[mNum];
for(int i = 0; i< mNum; i++) {
mList[i] = sc.nextInt();
}
for(int i = 0; i< mNum; i++) {
if (set.contains(mList[i]))
System.out.println(1);
else System.out.println(0);
}
}
}
문제를 풀 때 처음에는 ArrayList를 통해 풀었다. 내가 사용한 ArrayList의 contains메서드는 내부 값들을 전부 탐색을 하게되어 의 시간복잡도를 가지는 ArrayList의 contains메서드를 사용하니 이클립스에서는 잘 돌아가던 코드가 백준에서는 런타임 에러가 발생하였다.
그리하여 시간복잡도를 줄이기 위해 Binary Search를 구현하여 테스트를 해보았더니 결과가 통과되는 것을 확인하였다.
그 외에도 HashSet을 사용하여 문제를 풀어보았다. HashSet 또한 문제는 통과할 수 있었으나 Binary Search와 비교하였을 때 시간이 2배이상 늘어난 것을 확인할 수 있었으며 메모리 사용량 또한 더 많이 사용하는 것을 확인할 수 있었다.
맨 아래에 위치한 테스트는 ArrayList를 사용하여 런타임 에러가 발생한 결괴, 중간 위치한 테스트는 Binary Search를 사용하여 만든 코드의 결과, 맨 위에 위치한 테스트 결과는 HashSet을 사용하여 테스트한 결과이다.