※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
요약
첫 번째로 N개의 숫자 리스트가 주어지는데, 이것은 상근이가 가지고 있는 카드들이다.
두 번째로 M개의 숫자 리스트가 주어지는데, 이것은 각 숫자를 상근이가 가지고 있는지 여부를 확인한 후 가지고 있으면 1을, 아니면 0을 순서대로 출력한다.
기본적인 로직은 단순히 첫 번째 숫자들을 리스트 같은데 넣고 두 번째 숫자들을 하나씩 꺼내서 리스트에 존재하는지 확인해서 출력하는 것일 것이다.
그러나 이렇게 하면 시간 초과가 뜨게 된다.
배열로 만들어 for문으로 하나씩 순회해도 최악의 경우 500,000 x 500,000 = 250,000,000,000번 확인해야 하며, ArrayList에 넣어서 indexOf 등으로 확인해도 내부 로직은 비슷하니 역시 시간 초과이다.
HashSet 이용
자바에서 제공하는 HashSet이라는 것은 중복을 허용하지 않으면서 자료들을 저장한다. 객체의 해시코드 값을 이용하기 때문에 검색 속도가 매우 빠르다.
int N = Integer.parseInt(br.readLine());
HashSet<Integer> hands = new HashSet<>();
String[] tmp_hands = br.readLine().split(" ");
for(String n : tmp_hands){
hands.add(Integer.parseInt(n));
}
int M = Integer.parseInt(br.readLine());
String[] targets = br.readLine().split(" ");
for(String target_ : targets){
int target = Integer.parseInt(target_);
sb.append(hands.contains(target) ? 1 : 0);
sb.append(" ");
}사용법도 간단하다. 처음 주어진 숫자들을 HaseSet에 add한 다음, 두 번째로 주어진 숫자들을 하나씩 꺼내서 HashSet에 contains 메소드를 이용하여 존재 여부를 확인한다.
이진 탐색 이용
이진 탐색(Binary Search)라는 방식도 사용할 수 있다.
기존의 탐색 방식이 처음부터 끝까지 순서대로 훑다가 일치하는 값을 찾아내는 것이었다면, 이진 탐색은 배열을 반틈씩 범위를 줄여가며 빠르게 찾아낸다.
다만 탐색 전 정렬이 필수적이다.
원리를 간단히 설명하자면, 오름차순으로 데이터가 정렬된 상태에서 중앙값을 찾고자 하는 값(이하 타겟값)과 비교한다. 운이 좋다면 바로 일치할 것이고 탐색은 종료된다.
만약 타겟값이 중앙값보다 크다면 현재 중앙값 기준 배열의 왼쪽은 전혀 살펴볼 필요가 없게된다. 오른쪽 반틈에서 다시 중앙값을 찾은 후 타겟값과 중앙값의 크기 비교…를 반복한다.
별거 아닌것 같지만 데이터의 크기가 커지면 차이가 매우 커진다.
데이터가 100억개 있다고 가정하자.
순서대로 하나씩 찾는 선형 탐색의 경우는 최악의 경우(찾고자 하는 값이 마지막에 있을 때) 데이터를 100억개 모두 검사해야한다.
그러나 이진 탐색은 검색 한번에 범위가 절반씩 줄어드므로 횟수를 구하는 공식인 \(log_2 n\)에 대입하여 계산하면 34번이 나온다.
100억번과 34번. 차이가 느껴지는가?
이진 탐색에 대한 자세한 것은 정리가 더 잘된 다른 글을 참고해보자
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[] hands = new int[N];
String[] tmp_hands = br.readLine().split(" ");
for(int i=0; i<N; i++){
hands[i] = Integer.parseInt(tmp_hands[i]);
}
Arrays.sort(hands);
int M = Integer.parseInt(br.readLine());
String[] targets = br.readLine().split(" ");
for(String target_ : targets){
int target = Integer.parseInt(target_);
sb.append(binSearch(hands, target) ? 1 : 0);
sb.append(" ");
}
System.out.println(sb.toString());
br.close();
}
public static boolean binSearch(int[] arr, int target){
int start = 0;
int end = arr.length - 1;
int mid;
while(start <= end){
mid = (start + end) / 2;
if(arr[mid] == target){
return true;
}else if(target < arr[mid]){
end = mid - 1;
}else{
start = mid + 1;
}
}
return false;
}
}이진 탐색용 메소드를 하나 만들어서 검색하고 있다. 한 단계마다 중앙값을 구해가면서 찾고자 하는 값이 나올때 까지 반복한다.
댓글