TIL_20230309

오늘 할 일

• LeetCode 데일리 문제 풀기
• Heart
  • 토큰 재발행 기능 수정 - 마이페이지에서 생기는 부분인지 확인 필요
  • 토큰 만료시 출력되는 예외 처리 로그 확인하기
  • OAuth2 로그인 실패시 생기는 예외 처리의 description 수정

오늘 배운 것

LeetCode 데일리 문제 풀기

• 오늘의 문제: 142. Linked List Cycle II(https://leetcode.com/problems/linked-list-cycle-ii/)
• 문제 조건
  • 연결리스트의 헤드가 주어지면 사이클이 시작되는 지점의 노드를 반환해야 한다. 만약 사이클이 없다면 null을 반환한다.
  • 목록에 다음 포인터를 계속 따라가다보면 다시 연결할 수 있는 노드가 있고 연결된 목록에 주기가 있다. 내부적으로 pos는 테일의 다음 포인터가 연결된 노드의 인덱스(0 인덱스)를 나타내는 데 사용된다. 주기가 없으면 -1이다. pos는 매개 변수로 전달되지 않는다.
• 문제 해결
  • 첫 번째 방법은 리스트를 사용하기 때문에 시간복잡도나 공간 복잡도가 썩 좋은 편은 아니다.
  • head에 있는 node들을 하나씩 리스트에 집어넣으면서 순회할 때, node가 존재한다면 cycle이 존재하는 것이므로 while문을 빠져나와서 해당 노드가 존재하는 인덱스에 있는 node를 리턴한다.
  • 만약 node가 null이거나 다음 node가 null이면 null을 리턴한다.
  • node를 ListNode 형태로 리스트에 추가하면 각 노드의 주소값이 저장되기 때문에 val가 같다고 하더라도 주소값으로 노드의 위치를 찾을 수 있기 때문에 정상 동작한다.
  • 두 번째 방법으로는 Floyd's Cycle Detection Algorithm(또는 토끼와 거북이 알고리즘)을 이용하기 때문에 O(n)의 시간복잡도를 가지는 알고리즘이다.
  • 한 칸씩 움직이는 turtle과 두 칸씩 움직이는 rabbit을 두어 cycle이 존재하는지 찾아본다. cycle이 존재한다면 turtle과 rabbit이 만나는 순간이 생기고, cycle이 존재하지 않는다면 node나 node.next 값이 null인 경우가 생긴다.
  • cycle이 존재함을 확인하면 turtle을 다시 시작점으로 옮기고 이번에는 turtle과 rabbit을 한 칸씩 이동시켜 만나게 되는 지점이 사이클의 시작점이다. 그 이유는 cycle 내에 특정 위치에 있는 rabbit으로부터 cycle 방향대로 이동한 거리와 head에서부터 cycle의 시작점에 도달하는 거리가 같기 때문이다.

GitHub - chaning49/LeetCode

Heart

• 토큰 재발행 기능 수정 - 마이페이지에서 생기는 부분인지 확인 필요
  • 현재 테스트를 위해 refresh token으로 사용자 권한을 검증하고 있기 때문에 access token의 만료 시간으로는 제어가 불가능하다. → 추후 access token을 사용한 사용자 권한 검증 방식으로 수정 필요함
• 토큰 만료시 출력되는 예외 처리 로그 확인하기
  • 상동
• OAuth2 로그인 실패시 생기는 예외 처리의 description 수정
  • 따로 구현해놓은 부분이 있어서 동작 확인이 필요함
•  

느낀점

• 리트코드 문제에서 단일 연결리스트가 나와서 오랜만에 과거 기억을 끄집어냈습니다. 자료구조 수업에서 배운 내용을 제가 코드로 직접 해본 것이 몇 년만인지 모르겠지만 문제 해결에 대한 새로운 아이디어를 얻게 된 기분이라 좋습니다.
• 인증, 인가 관련된 부분은 아직도 헷갈립니다. 조금 더 잘하고 싶은데 레퍼런스를 어디서 얻어야 할지 고민됩니다. 책을 얼른 사볼까 싶기도 해요.

내일 할 일

• LeetCode 데일리 문제 풀기
• 알바 면접(선릉역)