Issues encountered
- Two sum 문제를 풀면서 어제 공부했던 투포인터 알고리즘을 적용시켰지만, 코드가 깔끔하지 않았고 효율성면에서 더 개선이 있다고 생각했다.
What I tried
- Leetcode 1. Two Sum Problem
- ChatGPT를 통해 내 코드의 개선할 부분에 대해 물어보았다.
- 우선 포인터 변수의 이름을 좀 더 명확하게
left
, right
으로 바꿀 필요가 있었다.
- 두 값의 합이
target
과 같을 때를 while문 terminate 조건으로 넣지 않고 안에서 if문으로 관리해서 if문에 걸렸을 때 바로 return해준다.
- ChatGPT를 통해 time complexity를 물어보았다.
- 만약 완전 탐색을 해서 이중 for loop을 돌렸다면 O(n^2)이 나왔겠지만, 투 포인터를 사용해서 O(n)이 나왔다.
- 그러나, hash map을 사용하면 O(1)의 시간 복잡도를 도출해낼 수 있었다.
- Hash로는 어떻게 풀까?
- JS에서는
new Map()
을 통해 key-value를 쉽게 담을 수 있는 객체를 만들어준다. key에는 값이, value에는 index를 넣는다
nums
array를 순회하면서 target
에서 각 value를 뺀 complement
라는 변수를 선언해준다. 이는 goal에 도달하기 위해 우리가 충족해야하는 값을 의미한다.
- 만약, Map에 해당
complement
가 있다면 (has()
를 통해 확인), 이의 value와 index를 즉시 반환하고 프로그램을 종료한다.
- 매번 순회할 때마다
set()
을 통해 key-value를 넣어준다.
- Leetcode 121. Buy and Sell Stock
- 이 문제에서도 투 포인터를 적용시켜봤지만, 성능면에서 썩 좋지 않았다.
- 단순히 for문을 한 번 돌면서
min_price
와 max_profit
을 트래킹 해주기만 하는 문제였다.
How I resolved the issues
- Two pointer algorithm
What I newly learned
- Two pointer를 복습하면서 hashmap의 활용도 공부할 수 있었다.
- JS Object
What to learn next
- 내일부터 노드 시작! 노드 공부도 하면서 JS 딥다이브 스터디를 병행하려고 한다.