[Java][Baekjoon]1920_수 찾기

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

시간제한 : 2 초에 주의해서 풀어야 하는 문제이다.

많은 사람들이 정렬과 탐색을 사용해서 문제를 푼 듯 하였지만,

나는 HashSet 자료구조를 사용해서 문제를 풀었다.

 

주어진 N개의 정수를 Set에 넣고, contains() 함수를 통해 M개의 정수가 포함되는지 여부를 구한다.

간단하기도 하고, 시간복잡도 O(1) 로 효율적이다.

 

public class Main_baek_1920_수찾기 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		Set<Integer> set = new HashSet<>();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		while (N-- > 0)
			set.add(Integer.parseInt(st.nextToken()));

		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine(), " ");

		while (M-- > 0) {
			int res = set.contains(Integer.parseInt(st.nextToken()))? 1 : 0;
			System.out.println(res);
		}
	}
}

 

 

추가로,

이분탐색을 통해서 풀어본 코드는 다음과 같다. ( O(log(n)) )

public class Main_baek_1920_수찾기_BinarySearch {
	
	public static ArrayList<Integer> list = new ArrayList<Integer>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		while(N-- > 0)
			list.add(Integer.parseInt(st.nextToken()));
		Collections.sort(list);
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine(), " ");
		
		while(M-- > 0) {
			int res = binarySearch(Integer.parseInt(st.nextToken()), 0, list.size()-1) ? 1 : 0;
			System.out.println(res);
		}
	}
	
	public static boolean binarySearch(int num, int sta, int end) {
		
		int mid = (sta + end)/2;
		
		if(end - sta <= 1 && list.get(sta) != num && list.get(end) != num)
			return false;
		
		if(list.get(mid) == num)
			return true;
		else if(list.get(mid) > num)
			return binarySearch(num, sta, mid-1);
		else 
			return binarySearch(num, mid+1, end);
	}
}

 

 

두 방법을 사용해 문제를 풀이한 결과는 다음과 같다.

 

---

www.acmicpc.net/problem/1920

1920번: 수 찾기