Leetcode: 직관적인 접근 방식의 2합

Spot-On Change Hotel 내부 기념품 가게의 자랑스러운 주인이 되어 보세요. 금전등록기를 닫으면 8유로가 초과된 것을 발견합니다. 손님이 정확한 잔돈을 받지 못한 것 같습니다. 이는 호텔의 평판을 손상시킬 수 있습니다. 이를 방지하기 위해 잘못된 변경의 미스터리를 해결하기로 결정했습니다. 상점의 현금 시스템을 열었을 때 두 개의 서로 다른 계좌에서 오류가 발생한 것을 발견했습니다!

당신은 계획을 세웁니다. 각 방을 방문하여 손님에게 가게에서 받은 잔돈이 무엇인지 물어보고 두 방의 청구서가 틀린 것을 찾을 때까지 하십시오. 1층에 도착하자 한 손님이 거스름돈으로 4유로를 받았다고 보고했습니다. 4유로에 더하면 8이 되는 숫자를 찾아야 한다고 계산했습니다. 2층으로 이동하면 손님의 잔돈은 5유로입니다. 4 + 5는 9가 되니 이게 될 리가 없지… 5층, 6… 10층, 안 돼, 안 돼, 안 돼!

첫 번째 시도에서 값을 찾지 못했기 때문에 2층으로 내려가 모든 손님에게 다시 변경 사항에 대해 물어보고 다음 시작 층의 값과 비교할 수 있도록 하기 시작합니다. 그것? 컴퓨터 과학에서는 이 검색 방법을 무차별 대입(brute force)이라고 하며, 배열의 한 항목을 다음 항목과 비교하여 작동하는 매우 느린 검색 방법입니다.

이것은 많은 시간을 소비하고 효율적이지 않습니다. 스팟온 체인지 호텔의 모든 층을 여러 번 오르내리는 것을 상상해보세요! 이는 귀하에게 실용적이지 않으며 컴퓨터에도 실용적이지 않습니다.

바닥을 오르락 내리락하는 것이 소프트웨어 프로그램에서 어떻게 될지 궁금하다면 JavaScript에서는 다음과 같이 보일 것입니다.

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

상황을 침착하게 평가한 후, 잔돈이 잘못된 두 손님을 찾는 더 효율적인 방법이 있다는 것을 알게 됩니다.

9유로가 x + y와 같다는 초기 수학적 직관을 다듬습니다. 약간의 연산을 적용하면 다음을 알 수 있습니다. x + y = 9는 y = 9 — x라고 말하는 것과 동일하며 이는 검색 효율성을 높일 때 큰 차이를 만듭니다.

전략에서 달라진 또 다른 점은 이제 손님이 알려주는 가치를 메모장에 적어두게 되므로 손님에게 같은 가치를 두 번 물을 필요가 없고, 지출을 하지 않아도 된다는 점입니다. 계단을 오르내리는 날. (엘리베이터가 고장나는 것은 정말 끔찍한 일입니다!)

새 도구를 손에 들고 1층으로 가는데 손님이 잔돈 5유로가 있다고 알려줍니다. 이를 {5:0}으로 기록하여 위치 0에서 값 5를 나타냅니다. 방정식에서 x를 5로 대체하면 y = 8–5를 계산하여 y = 3이 됩니다. 메모장은 여전히 비어 있으므로, 숫자 3은 기록되어 있지 않습니다. 이는 결과 8에 도달하기 위한 5의 보수가 됩니다. 그런 다음 메모장에 숫자 5를 적습니다. (보수가 아닌 현재 확인된 숫자를 항상 적는 것을 기억하십시오. 적어 둔 목표 숫자와 비교하기 위해 보수만 사용합니다). 2유로를 거스름돈으로 받았다고 언급한 두 번째 손님에게 다가가세요. 공식을 다시 적용하면: y = 8–2 => y = 6, 기록을 확인했는데 숫자 6을 찾을 수 없습니다. 따라서 기록에 2를 추가하면 이제 {5:0, 2:1}. 검색을 계속하자 다음 손님이 3유로의 거스름돈을 받았다고 보고했습니다. 다시 계산합니다: y = 8–3 => y = 5. 빙고! 메모장에 5가 기록되어 있습니다! 0층 손님은 2층 손님과 상호보완적이에요! 이 접근 방식을 해시 테이블이라고 하며 사용자와 컴퓨터 모두에게 훨씬 빠르고 효율적입니다. JavaScript에서는 다음과 같이 구현됩니다.

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

이는 Leetcode 의 쉬운 문제로, 뒤에 있는 개념을 이해한 후에만 쉬워집니다. 문제를 스스로 해결하고 그 뒤에 있는 직관을 구축하고 자신만의 비유를 만들고 검토하고 의사 코드를 작성해 보는 데 시간을 할애한 후 솔루션으로 넘어가는 것이 좋습니다.

제 비유가 두 가지 합계 챌린지의 개념을 더 잘 이해하는 데 도움이 되었기를 바랍니다.

다음에 또 만나요!