10815

날짜 : 2022. 09. 09

사용 언어 : python

 

문제

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

 

 

코드(기본모드 좌측버튼 -> 코드블럭 사용)

시간초과 코드(시간을 줄이기 위해 binary search 사용해야함)

import sys

n = int(sys.stdin.readline()) # 갖고 있는 숫자카드 개수 입력
arr_a = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline()) # m 입력
arr_b = list(map(int, sys.stdin.readline().split()))

for i in arr_b:
    if i in arr_a:
        print("1", end=" ")
    else:
        print("0", end=" ")

 

import sys

def search(arr, start, end, target):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target: # 중간값과 target이 일치할 경우
            return 1
        elif arr[mid] > target: # 중간값이 target보다 클 경우 -> left 이동
            end = mid - 1
        else: # 중간값이 target보다 작은 경우 -> right 이동
            start = mid + 1
    return 0


n = int(sys.stdin.readline()) # 갖고 있는 숫자카드 개수 입력
arr_a = list(map(int, sys.stdin.readline().split()))
arr_a.sort() # 정렬
m = int(sys.stdin.readline()) # m 입력
arr_b = list(map(int, sys.stdin.readline().split()))

for i in arr_b:
    if search(arr_a, 0, n-1, i):
        print("1", end=" ")
    else:
        print("0", end=" ")

 

알게된 점

- 코테 준비하면서 되도록이면 시간초과 케이스를 생각하자

- 일반 탐색보단 이분탐색 등 다양한 알고리즘을 활용하자

- 재귀보다는 반복문이 더 쉬운것 같다;;

 

 

참고 사이트

- 없음