[백준] 수 찾기 (이진 탐색 , Binary Search, Buffer, sort(), 1920번, Java)

 

문제설명

입력 & 출력

 

나의 풀이

 

이번 문제는 N개의 배열에서 M배열의 요소가 존재하는지 판단하는 문제입니다.

 

문자열에서 숫자를 찾는 방식을 사용할 수도 있지만, 문자열에서 숫자를 찾는 방식은 비효율적입니다. 따라서 이진 탐색을 사용하면 시간 복잡도를 크게 줄일 수 있습니다.

 

 

main문에서는 먼저 빠른 입력과 출력을 위해서 Buffer클래스를 사용하여 입력과 출력을 받아줍니다.

 

StringTokenizer를 사용하여 공백을 구분하고 배열에 저장해 주고, 이진탐색에서 선행되어야 하는 정렬을 수행해줍니다.

 

그리고 이진 탐색함수로 받은 결과를 StringBuilder를 사용하여 결과를 추가해 줍니다.

 

이진탐색을 수행할 binarySearch 함수에서는 이진 탐색의 동작 방식인 시작점 left와 끝점 right을 지정해 주고, 두 점이 교차하지 않을 때까지 반복을 해줍니다.

 

그러면 while문에서는 계속해서 값을 비교하고 절반을 줄여감으로써 빠른 검색을 할 수 있습니다.

 

주석을 자세히 달아놔서 따로 설명은 안 하지만 자세한 동작 방식은 아래의 포스팅에서 확인하 실 수 있습니다.

 

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

[Algorithm] 이진 탐색 알고리즘 : 데이터 정렬과 검색 최적화 (Binary Search, Java)