For Programmer

백준 10816번 파이썬 문제풀이(숫자 카드2) - 이분탐색 본문

코팅테스트/백준 문제 모음

백준 10816번 파이썬 문제풀이(숫자 카드2) - 이분탐색

유지광이 2022. 3. 29. 23:01
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
Comments