목록이분 검색 (1)

늘 겸손하게

백준 1920 ( Java )

수 찾기 N 개의 수를 입력받고 M개의 숫자가 주어졌을 때 해당 숫자가 N 개의 숫자들 중에 존재하는지 판별하는 문제. 문제 풀이 N 과 M의 범위가 1 이상 100,000이다. 그러므로 선형 검색(순차 검색)으로 코드를 짜면 시간제한에 걸릴 확률이 높다. 정수를 찾을때는 이분 탐색 (binary search) 알고리즘을 적용하여 검색을 하자. 그리고 모든 정수는 -2^31 보다 크거나 같고 2^31보다 작다는 제한이 있다. int 자료형의 범위는 -2^31 -1 ~ 2^31 - 1 이므로 음수 부분에서 걸린다. 그러므로 자료형을 long 형으로 해주자. 이분 탐색은 정렬된 배열에서 가능하므로 입력받은 N 개의 정수를 배열로 받아 정렬시키는 일부터 한다. import java.util.Arrays; 를 ..
코딩 문제/백준 2021. 7. 18. 14:14
이전 Prev 1 Next 다음