백준 1920 JAVA

문제 링크

1920 수 찾기
실버 4
이분탐색, 자료구조

풀이

풀이 1. Set을 사용하여 contains()로 해당 숫자 포함 여부를 찾는다.
풀이 2. 이분탐색을 사용하여 탐색한다.

실수 포인트

1. ArrayList 내부동작
   처음에는 완전탐색으로 풀면 백퍼 시간초과가 날것 같아서 ArrayList의 contains()를 사용하여 문제를 풀이 하였으나 ArrayList의 contains()함수 역시 내부적으로 완탐을 이용하여 구현되어있었다. Set 사용하라는 힌트를 받고 Set의 contains()를 사용하였으나 틀렸습니다.

- ArrayList의 시간 복잡도
add,get == O(1)
remove,contains == O(n)

- HashSet의 시간 복잡도
add,contains == O(1)
next == O(h/n) //h는 테이블 용량

2. HashSet 내부동작
   Set은 객체를 중복해서 저장할 수 없다.
   HashSet, TreeSet, LinkedHashSet이 있는데 HashSet은 순서를 보장하지 않고 TreeSet은 오름차순으로 데이터를 정렬한다(null을 허용하지 않는다.) LinkedHashSet은 입력된 순서대로 데이터를 관리한다.
   내가 사용한 HashSet에서의 contains()는 key의 Hash 값을 가진 object가 null인지 아닌지만을 판단하여 O(1)의 시간복잡도를 가진다.

Hash Table : key-value패턴으로 요소를 저장할 수 있음.

key와 value를 매핑시키는 과정을 hasing이라고 부른다. hashing을 실행하는 것을 해시 함수라고 부른다.

index가 숫자로 이루어져있는 Array나 List와 달리 숫자,문자열,파일등을 받아와 key를 O(1)시간만에 찾을 수 있다. 데이터를 저장할 위치를 간단한 연산으로 구하는 것. 즉 저장된 키 값에 따라서 특정 해시값을 만들어 내어 그것을 인덱스로 사용한다. 그럼 값을 추가,삭제할때도 해당 해시값을 통해 접근하게 된다 O(1). HashSet은 일반적으로 key를 value에 매핑할 필요가 없을 때 사용된다. HashSet은 내부적으로 HashMap을 사용하여 요소를 저장한다. 요소 자체는 key로 사용되며 해당하는 value와 관계가 없다.

읽어보면 좋을 글 : [https://joel-dev.site/74](HashMap/HashSet 원리)

코드 (java)

1. HashSet을 사용하는 방법

import java.util.*;

public class Main {
	static Scanner scan=new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		int n=scan.nextInt();
		Set<Integer> list=new HashSet<>();
		for(int i=0;i<n;i++) {
			list.add(scan.nextInt());
		}
		
		int m=scan.nextInt();		
		for(int i=0;i<m;i++) {
			int find=scan.nextInt();
			if(list.contains(find)){
				sb.append("1\n");
			}else sb.append("0\n");			
		}
		
		System.out.print(sb);
	}

}

2. 이분탐색을 사용하는 방법

이분탐색의 시간복잡도는 O(logn)이다.

import java.util.Arrays;
import java.util.Scanner;

public class bj1920_2 {
	static Scanner scan=new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();

	public static void main(String[] args) {
		int n=scan.nextInt();
		int[] arr=new int [n];
		for(int i=0;i<n;i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr);
		
		int m=scan.nextInt();	
		int [] arr2=new int[m];
		for(int i=0;i<m;i++) {
			arr2[i]=scan.nextInt();		
		}

		for(int i=0;i<m;i++) {
			boolean flag=false;
			int start=0;
			int end=n-1;
			while(start<=end) {
				if(flag)break;
				int mid=(start+end)/2;
				if(arr2[i]>arr[mid]) {
					start=mid+1;
				}else if(arr2[i]<arr[mid]) {
					end=mid-1;
				}else flag=true;
			}
			if(flag)sb.append("1\n");
			else sb.append("0\n");
		}
		
		
		
		System.out.print(sb);
	}
}