๐ญ ๋ฌธ์ ์ดํด
๋ ๊ฐ์ ์ ์ ๋ฆฌ์คํธ a, b๊ฐ ์ฃผ์ด์ง๊ณ ,
b์ ๋ชจ๋ ์์๋ฅผ ๋น๊ตํ๋ฉฐ a์ ์กด์ฌํ๋ ์ง ์ฌ๋ถ๋ฅผ 1๊ณผ 0์ผ๋ก ์ถ๋ ฅํ๋ ๋ฌธ์ ์ด๋ค.
๋ฌธ์ ์์ฒด๋ ๊ฐ๋จํ์ง๋ง ์์ ํ์์ ์ํํ๋ฉด 105 * 105 = 1010 ์ผ๋ก ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๊ฒ ๋๋ค.
์ด ๋ฌธ์ ๋ ๋ ๊ฐ์ง์ ํด๊ฒฐ ๋ฐฉ๋ฒ์ด ์๋ค.
1. ์ด๋ถ ํ์์ ํตํด ๋ฆฌ์คํธ b์์ ์์๋ฅผ ํ์ํ๋ ์๊ฐ์ log(n)์ผ๋ก ์ค์ธ๋ค.
2. set()์ in ์ฐ์ฐ์๋ O(1)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค๋ ํน์ง์ ์ด์ฉํ์ฌ ๋ฆฌ์คํธ b๋ฅผ set์ผ๋ก ์ ๋ ฅ๋ฐ์ ํ, in ์ฐ์ฐ์๋ก ํ์ํ๋ค.
https://twpower.github.io/120-python-in-operator-time-complexity
๊ตฌํ ์ธ์ด: Python
1. Binary Search
import sys
r = sys.stdin.readline
def binary_search(num, n_arr):
left = 0
right = len(n_arr)-1
while left <= right:
mid = (left + right) // 2
if n_arr[mid] < num:
left = mid + 1
elif num < n_arr[mid]:
right = mid - 1
else:
return 1
return 0
n = int(r())
n_arr = list(map(int, r().split()))
n_arr.sort()
m = int(r())
m_arr = list(map(int, r().split()))
for num in m_arr:
print(binary_search(num, n_arr))
2. set ์๋ฃ๊ตฌ์กฐ ํ์ฉ(์๊ฐ์ด ์ ๋ฐ ์ด์ ์ค์ด๋ฌ!!๐)
import sys
r = sys.stdin.readline
n = int(r())
n_set = set(map(int, r().split()))
m = int(r())
m_arr = list(map(int, r().split()))
for num in m_arr:
print(1 if num in n_set else 0)
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 10815 ์ซ์ ์นด๋ / ์ด๋ถํ์ (0) | 2021.02.09 |
---|---|
[BOJ] ๋ฐฑ์ค 2805 ๋๋ฌด ์๋ฅด๊ธฐ / ์ด๋ถํ์ (0) | 2021.02.09 |
[BOJ] ๋ฐฑ์ค 9205 ๋งฅ์ฃผ ๋ง์๋ฉด์ ๊ฑธ์ด๊ฐ๊ธฐ / BFS (0) | 2021.02.08 |
[BOJ] ๋ฐฑ์ค 2573 ๋น์ฐ / BFS (0) | 2021.01.14 |
[BOJ] ๋ฐฑ์ค 2468 ์์ ์์ญ / BFS (0) | 2021.01.13 |