두 포인터, 표 없이
왜 중요한가 "더해서 X가 되는 둘 찾기"에는 유명한 답이 있어요: 모든 걸 집합에 넣고 짝을 찾아보기. 빠르고, 모든 데이터의 사본이 필요해요. 데이터가 정렬돼 있으면 메모리가 거의 필요 없어요.
선물 서비스가 서로 다른 상품 둘의 묶음을 정해진 묶음 가격에 팔아요. 상품 가격표는 정렬돼 있고, 반복이 없고, 여유 메모리가 아주 적은 내장 기기에 있어요. 묶음 가격에 대해, 가격을 더하면 정확히 그 가격이 되는 상품 쌍의 수가 필요해요.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)count_pairs(tape, target)를 쓰세요. tape는 오름차순으로 정렬되고 반복이 없는 정수 가격의 Tape예요. 서로 다른 항목 둘을 더해 정확히 target이 되는 쌍이 몇 개인지 반환하세요(각 쌍은 한 번씩 세요). 예산: 항목 20,000개에서 최대 60,000개의 값을 읽고, 함수가 도는 동안 작업 메모리를 최대 16,000바이트 쓰세요(tracemalloc으로 재요. 가격 20,000개의 집합이나 리스트는 150,000바이트가 넘어요). len(tape)는 공짜예요.
이 연습은 곧 열려요
앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.
이 브라우저가 learn.floati.life의 쿠키를 막고 있어서, 여기서 마친 레슨들이 순서대로 열리지 않아요. 이 사이트의 쿠키를 허용하고 새로고침하세요.