[TIL] Leetcode 문제 풀이

김시원·2023년 4월 13일
0

TIL

목록 보기
2/50

Issues encountered

  1. Two sum 문제를 풀면서 어제 공부했던 투포인터 알고리즘을 적용시켰지만, 코드가 깔끔하지 않았고 효율성면에서 더 개선이 있다고 생각했다.

What I tried

  1. Leetcode 1. Two Sum Problem
    1. ChatGPT를 통해 내 코드의 개선할 부분에 대해 물어보았다.
      1. 우선 포인터 변수의 이름을 좀 더 명확하게 left, right으로 바꿀 필요가 있었다.
      2. 두 값의 합이 target과 같을 때를 while문 terminate 조건으로 넣지 않고 안에서 if문으로 관리해서 if문에 걸렸을 때 바로 return해준다.
    2. ChatGPT를 통해 time complexity를 물어보았다.
      1. 만약 완전 탐색을 해서 이중 for loop을 돌렸다면 O(n^2)이 나왔겠지만, 투 포인터를 사용해서 O(n)이 나왔다.
      2. 그러나, hash map을 사용하면 O(1)의 시간 복잡도를 도출해낼 수 있었다.
    3. Hash로는 어떻게 풀까?
      1. JS에서는 new Map()을 통해 key-value를 쉽게 담을 수 있는 객체를 만들어준다. key에는 값이, value에는 index를 넣는다
      2. nums array를 순회하면서 target에서 각 value를 뺀 complement라는 변수를 선언해준다. 이는 goal에 도달하기 위해 우리가 충족해야하는 값을 의미한다.
      3. 만약, Map에 해당 complement가 있다면 (has()를 통해 확인), 이의 value와 index를 즉시 반환하고 프로그램을 종료한다.
      4. 매번 순회할 때마다 set()을 통해 key-value를 넣어준다.
  2. Leetcode 121. Buy and Sell Stock
    1. 이 문제에서도 투 포인터를 적용시켜봤지만, 성능면에서 썩 좋지 않았다.
    2. 단순히 for문을 한 번 돌면서 min_pricemax_profit을 트래킹 해주기만 하는 문제였다.

How I resolved the issues

  1. Two pointer algorithm

What I newly learned

  1. Two pointer를 복습하면서 hashmap의 활용도 공부할 수 있었다.
  2. JS Object

What to learn next

  1. 내일부터 노드 시작! 노드 공부도 하면서 JS 딥다이브 스터디를 병행하려고 한다.

0개의 댓글