λ¬Έμ
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
νλ¦° λ΄ νπ¦·
# 1920. μμ°ΎκΈ°
import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, sys.stdin.readline().split()))
M = int(input())
arr_2 = list(map(int, sys.stdin.readline().split()))
result = []
for j in range(M):
one = []
for i in range(N):
if arr[i] == arr_2[j]:
one.append(1)
break
else:
one.append(0)
# print(one)
cnt = 0
for k in one:
if k == 1:
cnt += 1
if cnt >= 1:
result.append(1)
else:
result.append(0)
for k in result:
print(k)
ꡬμ§κ΅¬μ§νκ² μ§κΈ° λ¬μΈμ΄ λλ²λ¦° λ,,,,
λ¨κ³λ³ νμ΄λ‘ μλ€μ΄κ°κ³ μ±κ³΅λ₯ λ‘ λ€μ΄κ°μ μ νμ΄μ Έ μλκ±° νμ΄κ°μ§κ³
μ΄λ€ λ°©μμΌλ‘ νμ΄μΌνλμ§ ννΈ(μ΄μ°¨μ λ°°μ΄μ΄λ€, μ λ ¬μ΄λ€, μ΄μ§νμμ΄λ€ μ΄λ°κ±°)κ° μμ΄μ μ΄μΉ΄μ§ νλ€κ°
μ°ΎμμΌν κ°μ΄ μ£Όμ΄μ§ arr_2 리μ€νΈλ₯Ό λλΌλ©΄μ arrμ λ리λ μμ νμμΌλ‘ μ°Ύμμ μμΌλ©΄ λν΄μ£Όλ©΄ λκ² λ€..
μΆμκ³ λ¬΄μ¨μΌλ‘ μΈλ±μ€ μμμ€λΈλ μΈμ§λ μλκ³ νλ²μ μ±κ³΅νλλ.... νλλ°.... μ μΆνλλ°...
νλλ° μκ°μ΄κ³Όκ° λλ²λ Έλ€ γ γ νΉμλ λͺ°λΌμ import sysλ‘λ λ°κΏλ΄€λλ° μ€ν¨....γ γ
μμ λ λ΄ νπ¦·
λ°±μ€μμ νλ€κ° λ§νλ©΄ μ§λ¬Έκ²μν λ€μ΄κ°μ μ’ μ’ ννΈλ₯Ό μ»λλ°
λμ²λΌ ꡬμ§κ΅¬μ§νκ² νΈλ μ¬λμ΄ μμκ³ γ γ γ γ γ γ γ γ γ γ γ γ γ
setμ μ¬μ©νμ¬ μ λ ₯λ°μ μκ°μ μ κ² κ±Έλ¦¬κ² νλ λ°©λ²μ΄λ μ΄μ§ νμμ μ¬μ©νμλ€!!
κ·Έλ¬κ³ 보λ μ΄μ§ νμμ μ΄μ©νλ©΄ λμλλ° νΌμμ λΈλ‘λ Έλ§μ€(무μ§μ±)μΌλ‘ νκ³ μμλ€....
κ·Έλμ λ¨Όμ ν΄λ³Έ set() μΌλ‘ μ λ ₯ λ°κΈ° =>
N = int(input())
arr = set(map(int, input().split())) # μΆλ ₯ μκ°μ μ€μ΄κΈ° μν΄ set λ°μ
M = int(input())
arr_2 = list(map(int, input().split()))
for i in arr_2:
if i in arr: print(1)
else: print(0)
κ²°κ³Όλ μ±κ³΅~~~~~
setμ μμ£Ό μ μ°λ€λ³΄λ μ΄λ€ λΆλΆμμ μΈμ§ λͺ°λλλ°
μ λ ₯μ setμΌλ‘ λ°μ μ¬μ©νλ€λ μ μ μκ² λμλ€!!
μ΄μ§νμμΌλ‘ νμ λ΄ νπ¦·
λ λ€λ₯Έ λ°©λ²μ€μ νλμΈ λ°μ΄λ리 μμΉλ₯Ό ν΅ν λ°©λ²λ λ§μ΄ 보μ¬μ λμ ν΄ λ³΄μλ€~~
N = int(input())
arr = list(map(int, input().split()))
arr.sort() # μ΄μ§νμμ μ λ ¬λ κ²λ€ νμνλλ° μ΄ λΆλΆ κΈ°μ΅μ λͺ»ν΄μ 무ν 루νλ‘ λͺλ² λ€λ
μλ€
M = int(input())
arr_2 = list(map(int, input().split()))
for i in arr_2:
# λ°μ΄λ리 μμΉ νμ©νκΈ°(μ΄μ§νμ)
result = False
start = 0 # μμ μΈλ±μ€
end = N - 1 # λ μΈλ±μ€
while start <= end:
mid = ((start + end) // 2) # μ€κ°κ°μ μμΉμ ν΄λΉνλ μμ λͺ©ν λΉκ΅ν΄ λκ°
if i == arr[mid]: # μ€κ°κ°κ³Ό λͺ©νκ°μ΄ κ°λ€λ©΄
result = True
break
elif i > arr[mid]:
start = mid + 1
else:
end = mid - 1
if result:
print(1)
else:
print(0)
μνμλ λμ€κΈ°λ νμ§λ§ μ€λλ§μ μ΄μ§νμμ μ¬μ©ν΄μ κ³μ νλ¦°κ°μ΄ λμ€κ³
무ν루νλ‘ μ μ λ¨ΌλλΌμ΄μλλΌ λ€λ μλ€....
μ€κ°κ°κ³Ό λͺ©νκ°μ λΉκ΅νλ©΄μ μμμ μ΄ λ§μ§λ§μ λ³΄λ€ λμ΄μλ©΄ μ’ λ£λλ κΈ°μ 쑰건μ μ€μ νμλ€!!!!
μ°Έκ³ ν¨λ©΄ μ’μ κ°λ λ€ βοΈ
1) μ΄μ§ κ²μ(Binary Search)
: μλ£μ κ°μ¨λ°μ μλ νλͺ©μ ν€ κ°κ³Ό λΉκ΅νμ¬ λ€μ κ²μμ μμΉλ₯Ό κ²°μ νκ³ κ²μμ κ³μ μ§ννλ λ°©λ²
=> λͺ©μ ν€λ₯Ό μ°Ύμ λκΉμ§ μ΄μ§ κ²μμ μνμ μΌλ‘ λ°λ³΅ μνν¨μΌλ‘μ¨ κ²μ λ²μλ₯Ό λ°μΌλ‘ μ€μ¬κ°λ©΄μ λ³΄λ€ λΉ λ₯΄κ² κ²μμ μννλ€
- μ΄μ§ κ²μμ νκΈ° μν΄μλ μλ£κ° μ λ ¬λ μνμ¬μΌ νλ€(μ λ ¬μ΄ μλλΌ λ€μ μκ° μμ μλ³΄λ€ μ»€λ²λ¦¬λ©΄ μ€λ°μλ.. μ°Ύμ μκ° μμ!!!!!! μ£Όμ!!!!!!!!1..)
- κ²μ κ³Όμ
- μλ£μ μ€μμ μλ μμλ₯Ό κ³ λ₯Έλ€
- μ€μ μμμ κ°κ³Ό μ°Ύκ³ μ νλ λͺ©ν κ°μ λΉκ΅νλ€
- λͺ©νκ°μ΄ μ€μ μμμ κ°λ³΄λ€ μμΌλ©΄ μλ£μ μΌμͺ½ λ°μ λν΄μ μλ‘ κ²μμ μν, ν¬λ€λ©΄ μλ£μ μ€λ₯Έμͺ½ λ°μ λν΄μ μΈλ‘ κ²μμ μν
- μ°Ύκ³ μ νλ κ°μ μ°Ύμ λκΉμ§ 1~3μ κ³Όμ μ λ°λ³΅νλ€
- μ°Ύλλ€λ©΄ μ±κ³΅, λͺ» μ°ΎμΌλ©΄ μ€ν¨
- ꡬν
- κ²μ λ²μμ μμμ κ³Ό μ’ λ£μ μ μ΄μ©νμ¬ κ²μμ λ°λ³΅ μννλ€ => whileμ μ’ λ£ μ‘°κ±΄μ μ μ€μ νκΈ°
- μ΄μ§ κ²μμ κ²½μ°, μλ£μ μ½μ μ΄λ μμ κ° λ°μνμ λ λ°°μ΄μ μνλ₯Ό νμ μ λ ¬ μνλ‘ μ μ§νλ μΆκ° μμ μ΄ νμ
# μ΄μ§ κ²μ μκ³ λ¦¬μ¦
def binarySweach(a, N, key):
start = 0 # μμμ
end = N -1 # μ’
λ£μ
while start <= end:
middle = (start + end) // 2 # λͺ«μΌλ‘ νλ μ΄μ : λλκΈ° μ°μ°μλ₯Ό μ¬μ©νλ©΄ .0μΌλ‘ floatλκ±Έλ
if a[middle] == key: # κ²μ μ±κ³΅
return true
elif a[middle] > key:
end = middle - 1
else:
start = middle + 1
return flase # while λ¬Έμ λ€ λμλλ°λ μ°Ύμ§λͺ»νλ€λ©΄ κ²μ μ€ν¨
'algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
swea 4875. λ―Έλ‘ (μ¬λ°©νμ & DFS) (0) | 2023.08.19 |
---|---|
swea 4874. Forth (νμ νκΈ°λ² κ³μ°νκΈ°) (0) | 2023.08.19 |
swea 4875. λ―Έλ‘(dfs & λΈν νμ) (0) | 2023.08.15 |
[λ°±μ€/μ€ν] 9012. κ΄νΈ (μ§κΈμ§κΈ π π π ) (4) | 2023.08.10 |
[λ°±μ€ - λΈλ£¨νΈ ν¬μ€]19532. μνμ λΉλλ©΄κ°μμ λλ€ (2) | 2023.08.09 |