For Programmer
백준 10816번 파이썬 문제풀이(숫자 카드2) - 이분탐색 본문
728x90
파이썬 딕셔너리 사용하면 쉽게해결 할 수 있으나 정렬 후 이분탐색으로 찾을려는 수 x의 양끝 인덱스를 찾아서 그 2개를 빼주고 1을 더하는 식으로 개수를 구했다. (python3로 제출하면 시간초과가 발생하고 pypy로 제출해야 시간초과발생하지 않습니다.)
N = int(input())
card = list(map(int, input().split()))
M = int(input())
saguen = list(map(int, input().split()))
card.sort()
for i in range(M):
s = 0
e = N - 1
ans_1 = 0
# 시작부분 찾기
while s <= e:
mid = (s + e) // 2
if card[mid] == saguen[i]:
ans_1 = mid
e = mid - 1
elif card[mid] > saguen[i]:
e = mid - 1
else:
s = mid + 1
s = 0
e = N - 1
ans_2 = 0
# 끝부분 찾기
while s <= e:
mid = (s + e) // 2
if card[mid] == saguen[i]:
ans_2 = mid
s = mid + 1
elif card[mid] > saguen[i]:
e = mid - 1
else:
s = mid + 1
if ans_1 == 0 and ans_2 == 0: # 둘다 0이라면(즉 해당 수가 없다면)
print(0, end=" ")
else:
print(ans_2 - ans_1 + 1, end=" ")
728x90
'코팅테스트 > 백준 문제 모음' 카테고리의 다른 글
백준 2805번 파이썬 문제풀이(나무 자르기) - 이분탐색 (0) | 2022.03.30 |
---|---|
백준 2792번 파이썬 문제풀이(보석상자) - 이분탐색 (0) | 2022.03.30 |
백준 10815번 파이썬 문제풀이(숫자 카드) - 이분탐색 (0) | 2022.03.29 |
백준 3020번 파이썬 문제풀이(개똥벌레) (0) | 2022.03.28 |
백준 2015번 파이썬 문제풀이(수들의 합 4) (0) | 2022.03.28 |
Comments