[BOJ] 1920번 수찾기 / 이분탐색 / 해시테이블

 

 

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

1920번: 수 찾기

 

 

수 찾기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

217313

66856

44340

30.018%

문제

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

출력

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

예제 입력 1 

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

예제 출력 1 

1
1
0
0
1

 

 

 

---

 

첫번째 제출 

n = int(input())
arr = list(map(int,input().split()))
m = int(input())
arrM = list(map(int,input().split()))

arr.sort()
max_size = arr.pop()
for x in arrM:
  if x <= max_size:
    print(1)
  else:
    print(0)

 

문제를 잘못 이해했다.

입력받은 N개의 정수가 1~N 까지의 수인데 순서만 섞인 입력인 줄 알았다.

테스트 케이스만 보고 내멋대로 해석하기,,

 

 

 

두번째 제출 

n = int(input())
arr = list(map(int,input().split()))
m = int(input())
arrM = list(map(int,input().split()))


for x in arrM:
    if x in arr:
        print(1)
    else:
        print(0)

시간초과가 나올걸 알았지만 일단 시도해봤다.

 

정확히 어떤 이유로 시간초과가 나는지 모르고

해결하려면 어떤걸 이용해야하는지 모르니까  공부해보자.

 

List 에서 in 연산자 성능

list 의 값이 커진다면 , in 연산자는 값을 다 하나하나 스캔 한다음 결과값을 반환하기때문에 오래걸린다. O(n) 

import time
a = list(range(1, 10000001))

start1 = time.time()
print(1 in a) # 첫번째 값
end1 = time.time()

start2 = time.time()
print(10000000 in a) # 마지막 값
end2 = time.time()

print(end1-start1)
print(end2-start2)


# 출력 
# True
# True
# 0.0012135505676269531
# 0.2061300277709961

 

맨 마지막 값을 검색했을 때는 처음부터 끝까지 10,000,000번을 검사한다. 

 

 

 

세번째 제출

n = int(input())
arr = set(map(int,input().split()))
m = int(input())
arrM = list(map(int,input().split()))

for x in arrM:
    if x in arr:
        print(1)
    else:
        print(0)

 

set 자료구조

- Mutable 자료형 (변경가능한 객체)

값이 변경이 일어날떄 객체의 값이 변경

- 중복X 

- 정렬X , 순서가 없음

- 선언  a = set() 

 

Set 에서 in 연산자 성능

시간복잡도 O(1)

Set도 자신이 가지고 있는 원소들은 뭐가 있는지 찾아봐야 할 텐데… 어떻게 Set에서의 자료 검색은 상수시간이 되는걸까?

 

 

해시 테이블

• (Key, Value)로 데이터를 저장하는 자료구조 중 하나
• 빠르게 데이터를 검색할 수 있다

해시 테이블이 빠른 검색속도를 제공하는 이유? 

• 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문
• 버킷(bucket)이란?
• 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

 

 

추가 제출 

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
m = int(input())
arrM = list(map(int,input().split()))

def binary(target):
    left = 0
    right = n-1 
    
    while left<=right:
        mid = (left+right)//2
        
        if arr[mid] == target:
            return True
        
        if arr[mid] < target:
            left = mid + 1 
        elif arr[mid] > target:
            right = mid - 1

for x in arrM:
    if binary(x):
        print(1)
    else:
        print(0)

 

이분 탐색

이진 탐색의 시간 복잡도는 O(logN)

오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘