[BOJ 백준] 수찾기(1920) Java

링크 : https://www.acmicpc.net/problem/1920

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

 

출력 : 

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력 : 

5
4 1 5 2 3
5
1 3 7 9 5

 

예제 출력 : 

1
1
0
0
1

 

접근법 : 

1) 어떻게 풀 것인가?

10만개의 숫자 배열 A가 주어지고 가 주어지고, 임의의 수 10만개가 주어질때, 그 수가 A에 포함된 수인지 찾아내야하는 문제이다. 단순하게 생각해보면 10만 * 10만의 시간복잡도를 가진다. 100억 정도의 시간복잡도로 백준 기준으로 간당간당하게 통과할수도 있다. 실제 완전탐색으로도 백준에서 Java 기준 5,000ms 미만으로 통과 가능.

 

그러나 삼성 SW검정시험이나 기타 다른 시험에서는 test case가 50개 이상 주어지는 경우가 많으므로 단순 완전탐색으로 풀 경우 시간초과가 날 확률이 높다. 

 

따라서 중급 이상으로 가려면 N이 10만 또는 100만이 주어진다면 보자마자 N 또는 logN의 시간복잡도가 되게하는 알고리즘을 떠올리는게 좋다.

일반적인 완전탐색 등으로 시간 복잡도가 N^2이상이 될 경우 시간초과가 발생할 수 있기 때문이다.

logN의 시간복잡도를 가진 자료구조 및 문제풀이 방법은 이진탐색, 우선순위큐, 인덱스드트리, 최저공통조상(LCA) 등이 있고, N의 시간복잡도는 DP, Stack을 활용한 풀이 등이 있다.

 

다시 돌아와서 문제를 한 문장으로 요약하면 10만 개의 데이터에서 가장 빠르게 원하는 값이 있는지 확인하는 문제이다.

가장 쉽고 빠르게 데이터에서 값을 찾는 방법으로는 "이진탐색 방법"이 있다.

 

Up / Down 게임을 생각하면 좋다.

1~50까지의 수 중에서 특정 수 x가 무엇인지 6번의 질문으로 찾아야하는 상황이 있다고 가정할때 아래와 같은 방법이 가장 효율적이다. x가 36이라고 가정했을 때,

 

질문1] 25                       답1] Up     -> 26~50의 중간값인 38을 질문

질문2] 38                       답2] Down -> 26~37의 중간값인 31을 질문

질문3] 31                       답3] Up     -> 32~37의 중간값인 34를 질문

질문4] 34                       답4] Up     -> 35~37의 중간값인 36을 질문

질문5] 36                       답5] 정답

 

1부터 쭉 완전탐색으로 물어봤다면 36번만에 찾을 수 있는 값을 5번만에 찾을 수 있었다.

 

마찬가지로 10만이라는 숫자가 있을때 단순 완전탐색으로는 10만개의 데이터를 다 뒤져야 찾을 수 있지만

이진탐색을 사용하면 log2N 만에 값을 찾을 수 있다. 검색 속도가 중요한 DB도 대부분 이진탐색 기반의 검색 방법을 이용한다. (B-Tree 기반의 Index Scan 이용)  

 

참고 : 이진탐색 위키피디아

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

 

2) 시간복잡도

이진탐색의 경우 log2N의 시간복잡도를 가진다. (실제 실행시간 Java - 540ms / C - 60ms)

 

3) 공간복잡도

정수의 범위가 2^31 ~ -2^31이므로 int로도 충분하다. int 자체가 32비트의 이진수이기 때문에 정확히 2^31 ~ -2^31가

int의 표현가능범위이다. 연습삼아 Long 으로 해봐도 메모리 자체는 충분하다.

long 기준으로 해도 8Bytes * 100000 = 800Kbytes 미만.

 

4) 풀면서 놓쳤던점

- for loop M이 들어가야할 자리에 N으로 잘못 넣어서 찾는데 한참걸렸다.

 → 입출력 등 기본 구조를 짤때 가장 집중.

 

5) 이 문제를 통해 얻어갈 것

이진탐색 직접 구현 연습. 삼성 SW검정시험 B형에서는 upper bound(동일한 값 없을 경우 비슷한 값 올림으로 찾음), lower bound(동일한 값 없을 경우 비슷한 값 내림으로 찾음) 등까지 쌩으로 구현할 수 있는게 좋다.

 

Java기준 ArrayList 로 자료형 선언할 경우 어떻게 Comparator 또는 Comparable overriding을 통해 데이터를 정렬할 수 있는지 연습. Cpp기준도 qsort의 compare 함수나 구조체의 operator overriding은 연습하는게 좋다.

 

이진탐색 구현과 merge sort 구현이 비슷하므로 연습하는 김에 삼성 SW검정시험 B형 이상을 원할 경우 C++로 merge sort까지는 구현할 수 있는 것 추천.

 

Java 코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

// 수찾기 백준 1920
public class Main {

	static int N, M;
	static int[] array;	
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		// 숫자를 받을 배열
		array = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		
		// 입력받은 숫자를 오름차순 정렬	
		Arrays.sort(array);
        // ArrayList<Long> 으로 선언했을 경우 Comparator를 통해 정렬하기
		// array.sort(new Comparator<Long>() {
		//	@Override
		//	public int compare(Long o1, Long o2) {
		//		if (o1>o2) return 1;
		//		return -1;
		//	}
		//});        
      	
		M = Integer.parseInt(br.readLine()); 
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int tmp = Integer.parseInt(st.nextToken());
            // int id = Arrays.binarySearch(arr, Integer.parseInt(st.nextToken()));
            // 라이브러리 binarySearch를 이용할 경우 (성능 더 좋음)
			bw.write(String.valueOf(binarySearch(tmp))+"\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	// num가 array에 있으면 1 return 없으면 0 return 하는 이진탐색 함수
	static int binarySearch(int num) {
		int start,mid,end;
		start = 0;		
		end = N-1;		
		while(start<=end) {
			mid = (start+end) / 2;
			int val = array[mid];
			if(num == val) return 1;
			if(num>val) {
				start = mid+1;
			}
			else {
				end = mid-1;
			}
		}
		return 0;
	}
}