250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- MinHeap
- 자료구조
- 백준
- Mask Processing
- BFS
- Reinforcement Learning
- dynamic programming
- AlexNet
- C++
- SIFT
- edge detection
- DP
- clustering
- sklearn
- IN
- 인공지능
- opencv
- 딥러닝
- image processing
- machine learning
- MySQL
- exists
- 강화학습
- classification
- 그래프 이론
- Python
- dfs
- canny edge detection
- 머신러닝
- TD
Archives
- Today
- Total
JINWOOJUNG
[ 자료구조-1920 ] 수 찾기(python) 본문
728x90
반응형
접근법
Array를 이용한 BST를 만들어서 접근하려고 했지만, 너무 과하고 시간이 문제여서 Binary Search를 유사하게 구현해서 접근하기로 하였다.
정답
import sys
import math
N = int(input())
inputs = list(map(int,sys.stdin.readline().split(" ")))
inputs.sort()
M = int(input())
array = list(map(int,sys.stdin.readline().split(" ")))
for i in range(0,M):
L = 0
R = N-1
flag = False
while L<=R:
mid = math.ceil((L+R)/2)
if( array[i] == inputs[mid]):
flag = True
break
elif( array[i] > inputs[mid]):
L = mid
if(array[i] > inputs[R]):break
else:
R = mid-1
if(array[i] < inputs[L]):break
if flag:
print("1")
else:
print("0")
첫번째로 받아오는 inputs는 sort()를 사용하여 정렬시켰다.
L,R을 배열의 양 끝 index로 설정하고 L이 R보다 같거나 작을 때 까지 반복하도록 하였다.
mid 즉, inputs list의 중앙값 계산 시 math.ceil()을 이용해 올림시켰다.
이때, L=R이여서 mid 값이 계속 같아져 무한 loop에 빠지는 경우를 방지하기 위해 비교할 값이 inputs[R]보다 크거나, inputs[L]보다 작은 경우를 예외처리 하였다.
728x90
반응형
'백준' 카테고리의 다른 글
[ 그래프 이론-2668 ] 숫자고르기(Python) (0) | 2023.12.30 |
---|---|
[ 자료구조-1253 ] 좋다(Python) (0) | 2023.12.29 |
[ 자료구조-1715 ] 카드 정렬하기(Python) (0) | 2023.12.28 |
[ 그래프 이론-10026 ] 적록색약(Python) (2) | 2023.12.28 |
[ 그래프 이론-1012 ] 유기농 배추(Python) (0) | 2023.12.25 |