4월 2주차 알고리즘 문제 - sliding window, integer trimming, 저장을 통한 연산 횟수 줄이기

목차

[금주의 문제] sliding window를 통해 더 적게 비교하기
trailing zeros 제거하는 다양한 방법
저장을 통해 연산 횟수 줄이기

[금주의 문제] sliding window를 통해 더 적게 비교하기

문제 링크
내 풀이
문제 요약
- list integer에서 key값과 좌우로 k만큼 떨어진 index로 구성된 list를 구하는 문제이다.(findKthDistanceIndices)
풀이 요약
- 기존 풀이
  - Time Complexity: $O(k*n)$
  - set을 이용해서 key가 발견되면 좌우 index range를 update하고, 최후에 sorted된 list를 반환하는 방식으로 구현했다.
- 개선 풀이
  - Time Complexity: $O(n)$
  - sliding window를 통해 update해야할 필요가 있는 index를 범위를 줄인다
  - 한 번만의 loop만으로 문제를 해결할 수 있다.

trailing zeros 제거하는 다양한 방법

문제 링크
내 풀이
문제 요약
- 문자열로 저장한 수에서 맨 뒤의 0들을 모두 제거하는 문제이다.
풀이 요약
- 내 풀이
  - 내 풀이는 input string을 list로 변환한 뒤 pop을 사용해 0을 제거하는 방식으로 구현했다.
  - 이는 python에서 list pop은 stack과 같이 동작하기 때문에 효율적이기 때문이다.
- 다른 풀이
  - rstrip을 사용한다
  - 수를 integer로 변환하고 뒤집었다가 다시 뒤집는다

저장을 통해 연산 횟수 줄이기

문제 링크
내 풀이
문제 요약
- integer array에서 subarrary를 삭제한 뒤에 전 구간에서 increasing하는 array가 되는 경우, 삭제한 subarray를 incremovable subarray라 한다. 이때 incremovable subarray의 개수를 구하는 문제이다.
풀이 요약
- Brute Force 풀이
  - Time Complexity: $O(n^3)$
  - 모든 subarray에 대해 잘라지지 않은 subarray가 increasing한지 확인하는 방법
- 개선 풀이
  - Time Complexity: $O(n^2)$
  - 모든 subarray들의 increasing 여부를 저장한다. 그런 다음 자르고 나서 좌 우가 increasing하고, 연결부가 increasing한 경우를 찾는다.

for i in range(len(nums)):
    for j in range(i, len(nums)):
        if isIncreasingSubarray.get((0, i - 1), True) and isIncreasingSubarray.get((j + 1, len(nums) - 1), True):
            if nums[j+1] > nums[i-1] if i > 0 and j < len(nums) - 1 else True:
                result += 1

2024-04-09