문제링크

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

문제 해석

for문

이 문제의 출력을 보면 그냥 N만큼 for문을 돌려서 최종값을 구할수 있는 문제이다.

이렇게 했을 경우 시간복잡도는 O(NM), 500,000 * 500,000 = 25 x 10^10 이다. 결국 시간초과가 날수 밖에 없다.

이분탐색

선형이 아니라 이분탐색으로 찾으면 M logN, 500,000 ??, 많아봤자 10^7임을 추측됨

풀이

중간값 출력

from bisect import bisect_left, bisect_right

N = int(input())
cards = sorted(map(int, input().split()))
M = int(input())
qry = list(map(int, input().split()))
ans = []


for q in qry:
    l = bisect_left(cards, q)
    r = bisect_right(cards, q)
    print(l, r)

전체코드

from bisect import bisect_left, bisect_right

N = int(input())
cards = sorted(map(int, input().split()))
M = int(input())
qry = list(map(int, input().split()))
ans = []


for q in qry:
    l = bisect_left(cards, q)
    r = bisect_right(cards, q)

    ans.append(1 if r - l else 0)


print(ans)

아스테리스크 출력

print(*ans)

join 출력

print(' '.join(map(str, ans)))

최종

참고로 N,M 변수는 쓰지 않으므로 _ 처리

사실 N,M의 진짜 의도는 c++같은 경우 값을 scanf를 통해 입력을 받으면 값을 하나하나씩 받아야 하는데 python은 input으로 입력값을 통째로 받아서 N,M을 쓸 필요가 없었다.

전체코드

from bisect import bisect_left, bisect_right

_ = int(input())
cards = sorted(map(int, input().split()))
_ = int(input())
qry = list(map(int, input().split()))
ans = []


for q in qry:
    l = bisect_left(cards, q)
    r = bisect_right(cards, q)

    ans.append(1 if r - l else 0)


print(*ans)
# print(' '.join(map(str, ans)))