[LeetCode: 01] Two Sum

뜬금없이 알고리즘이 풀고 싶었습니다,

그래서 LeetCode 1번을 한 번 풀어보겠습니다. 

링크는 요기입니다. 가서 한 번 풀어보세요.

뭔가 대게 어려워 보입니다.

이지인데 말이죠.

 

전 일단 이거 보고 딕셔너리가 생각났어요.

그 이유는... 지금부터 설명해보겠습니다.

 

지금은 조금더 보기 편하게 하기 위해서 KeyType은 Int ValueType은 String이지만..

KeyType은 Int Value Type도 Int라면.. 키 1의 값은 얼마 키 100의 값은  쉽게 쉽게 넣을 수 있잖아요?

뒤에 설명을 보면 더 와닿을꺼라 생각됩니다.

 

자 이제 천천히 생각해봅시다.

[1,5,8,11] 란 예시 배열이 있습니다. 그리고 주어진 합은 6이라고 가정해봅시다

만약에 1이 답이 되려면 5가 필요합니다.

그러면 일단.. 딕셔너리에서 키값이 5인 것을 찾습니다.

하지만 첫 번째 실행이니까 사전은 아무 값도 갖지 않을 겁니다.

그러면 키값 1은 0이란 value를 저장해줍니다. 

0인 이유는 인덱스를 반환하는 문제니까 나중에 키 값이 1인 값이 답이 될 때 인덱스를 반환하기 위해서입니다.

 

자 그럼 두 번째

5가 답이 되려면 1이 필요합니다.

그러면 아까처럼 딕셔너리에서 키값이 1인 것을 찾습니다.

아, 때마침 1인 값이 있네요. 

키값이 1인 녀석은 값을 0을 가지고 있네요.

 

그러면 0이랑 지금 인덱스인 1을 리턴하면 되겠네요.

 

설명이 조금 장황했지만

결국 딕셔너리에 [주어진 배열의 인덱스가 가지는 값: 주어진 배열의 인덱스] 이 딕셔너리를 이용해서 푸는 게 핵심입니다.

 

코드를 짜 봅시다.

 

코드에 대한 긴 설명은 안 하겠습니다.

위에 했던 설명을 한 줄 한줄 대입해보면 그대로 대입됩니다.

주어진 배열을 차례차례 돌면서 구해야 하는 합에 얼마나 모자란 지 찾고..

그 모지란 값이 키값으로 딕셔너리에 있는지 찾은 다음

있으면 그 키의 Value를 answer에 넣고 현재 인덱스도 answer에 넣고 반환한다,

 

한 번 돌려 봅시다.

 

 

자 일단 테스트 케이스만 돌려보면 잘됩니다.

추후에도 계속 풀면 아시겠지만..

저 테스트 케이스를 통과했다고 무조건 실행코드가 잘되는 건 아니지만

그래도 점검차 돌려보는 게 좋습니다.

그럼 테스트 케이스를 통과했으니 제출을 해봅시다.

오 통과되었네요.

통과가 되었으니 글을 이만 줄이겠습니다.

 

그럼 다음 시간에 또 다른 걸로 또다시 찾아뵙겠습니다