TIL_20230506

오늘 할 일

• LeetCode 데일리 문제 풀기

오늘 배운 것

LeetCode 데일리 문제 풀기

• 오늘의 문제: 1498. Number of Subsequences That Satisfy the Given Sum Condition Length(https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/)
• 문제 조건
  
  • 정수형 배열 nums와 정수 targer이 주어진다.
  • 숫자의 최소 및 최대 요소의 합이 목표값보다 작거나 같도록 숫자의 비어 있지 않은 연속 수를 반환한다. 답이 너무 클 수 있으므로 모듈 10^9 + 7로 반환한다.
• 문제 해결 과정
  
  • nums의 길이 최대가 10^5이므로 O(N^2)은 불가능하다.
  • 단순히 2중 for문을 사용하면 안될 것이다. 투 포인터로 푸는 문제이다. 그 이유는 각 사이클마다 누적합의 크기를 target과 비교했을 때, 더 작은 수가 아니면 왼쪽 인덱스를 증가하고, 그렇지 않다면 오른쪽 인덱스를 증가하면서 가능한 방법을 모두 찾아야 하기 때문이다.
  • 우선 배열을 오름차순 정렬하고, 2의 거듭제곱을 저장한 배열 pow를 1부터 2의 n - 1제곱까지 저장한다. 2의 거듭제곱이 나오는 이유는 집합의 성질 때문인데, 원소가 n개인 집합의 모든 경우의 수는 2^(n-1) - 1개이다. 한가지 예로 집합 {1, 2, 3}은 {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}으로 총 7개인데, 이는 공집합을 제외한 부분집합이기 때문이다.
  • 이 문제의 아이디어는 전체 집합에서 구할 수 있는 부분집합 중 target보다 큰 경우는 제외하는 것이므로 오름차순으로 정렬 후 첫번째 값과 마지막 값의 합을 target과 비교하면서 가능한 경우의 수를 찾는 것이다.
  • 그래서 투 포인터의 left와 right를 통해 포인터가 가리키는 값의 합이 target보다 크면 right를 감소시켜서 target에 해당하지 않는 부분집합을 제거한다고 생각하면 된다. 만약 target 이하라면 left - right에 해당하는 인덱스에 위치한 2의 거듭제곱 값을 res에 더해주면 된다.

느낀점

• 오늘은 가볍게 쉬어가는 하루를 보냈습니다. 가족들과 식사도 하고 낮잠도 자고 하면서 쉬는 하루로 보냈습니다.
• 리트코드 문제를 풀어봤는데, 꽤나 어려워서 도움을 받아 풀었습니다. 투 포인터와 슬라이딩 윈도우에 대해서 리트코드 덕분에 점점 알아가는 중입니다!

내일 할 일

• SK 자기소개서 첨삭 받고 작성하기