728x90
λ°˜μ‘ν˜•

문제

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. 자료의 쀑앙에 μžˆλŠ” μ›μ†Œλ₯Ό κ³ λ₯Έλ‹€
  2. 쀑앙 μ›μ†Œμ˜ κ°’κ³Ό 찾고자 ν•˜λŠ” λͺ©ν‘œ 값을 λΉ„κ΅ν•œλ‹€
  3. λͺ©ν‘œκ°’이 쀑앙 μ›μ†Œμ˜ 값보닀 μž‘μœΌλ©΄ 자료의 μ™Όμͺ½ λ°˜μ— λŒ€ν•΄μ„œ μƒˆλ‘œ 검색을 μˆ˜ν–‰, 크닀면 자료의 였λ₯Έμͺ½ λ°˜μ— λŒ€ν•΄μ„œ μ„Έλ‘œ 검색을 μˆ˜ν–‰
  4. 찾고자 ν•˜λŠ” 값을 찾을 λ–„κΉŒμ§€ 1~3의 과정을 λ°˜λ³΅ν•œλ‹€
  5. μ°ΎλŠ”λ‹€λ©΄ 성곡, λͺ» 찾으면 μ‹€νŒ¨

- κ΅¬ν˜„

  • 검색 λ²”μœ„μ˜ μ‹œμž‘μ κ³Ό μ’…λ£Œμ μ„ μ΄μš©ν•˜μ—¬ 검색을 반볡 μˆ˜ν–‰ν•œλ‹€ => 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 문을 λ‹€ λŒμ•˜λŠ”λ°λ„ 찾지λͺ»ν•œλ‹€λ©΄ 검색 μ‹€νŒ¨

 

728x90
λ°˜μ‘ν˜•

+ Recent posts