[誤答ノート/python]コード-記憶力テスト3

質問する

解けなかった理由

問題は

時間を超えることです.最初の試みでは,入力値の範囲を考慮せずに順次探索して解を求めたが,タイムアウトした.2つ目の試みでは,問題で入力値を昇順に並べ替えることに原因があると考え,バイナリ検索で解いたが,タイムアウトした.△問題のヘルプは見られませんでした.

バイナリ検索としてもタイムアウトしたのは、バイナリ検索の結果がif文をもう一度乗算し、値を検索し、値が見つからないときに印刷するため、True/Felseを返したからです.

に答える

バイナリ・ナビゲーションを行うには、ナビゲーションするリストをソートする必要があります.次に、検索する値が正の中間点(mid)より小さい場合は左側を参照し、検索する値がmidより大きい場合は右側を参照します.midが検索値になるまで、この手順を繰り返します.

n = int(input())
nums = list(map(int, input().split()))
m = int(input())
ques = map(int, input().split())

# 이진탐색으로 찾기
def findNum(start, end, arr, target):

    # 시작지점이 끝지점보다 작거나 같을 때까지 반복
    while start <= end:
        mid = (start + end) // 2    # 중간지점

        # 숫자를 찾았을 때 인덱스 값 반환
        if arr[mid] == target:    
            return mid + 1

        # 중간지점이 찾는 값보다 크면 왼쪽 부분 탐색
        elif arr[mid] > target:   
            end = mid - 1
            
        # 중간지점이 찾는 값보다 작으면 오른쪽 부분 탐색
        else:
            start = mid + 1
            
    return -1    # 찾는 숫자가 없으면 -1 반환

for n in ques:
    print(findNum(0, len(nums)-1, nums, n), end=' ')

もとのfor文の作成は以下のようになります.もう一度見てみると、本当に無心な手配でした.上のコードに比べて、もちろんもっと時間がかかります.for文ではif文で値が足りないと判別し、数値が見つかった場合numsリストでインデックスを再検索してインポートします.元気出して!

for n in ques:
	if findNum(0, len(nums)-1, nums, n):
    	print(nums.insert(n)+1, end=' ')
    else:
    	print(-1, end=' ')

レビュー

I/O値制限事項は必ず問題を読むときに確認してください.そして、実行速度を速める方法、最小限のコードを書く方法を考えて問題を解決します...!