5월 2주차 알고리즘 문제 - 과연 중간 과정은 꼭 필요할까?

목차

$O(n)$으로 배열 내 요소 간 최대 차이 구하기
필요 없는 중간과정 생략하기
3개의 distinct한 subarray를 구하는 방법

$O(n)$으로 배열 내 요소 간 최대 차이 구하기

문제 링크
내 풀이
문제 요약
- int array가 주어졌을 때, i < j이고 A[i] < A[j]인 경우에 A[j] - A[i]의 최대값을 구하라.
풀이 요약
- 기존 풀이
  - Time Complexity: $O(n^2)$
  - i < j이고 A[i] < A[j]인 경우에 A[j] - A[i]의 최대값을 구하라는 것은 A[j] - A[i]의 최대값을 구하라는 것과 같다.
  - 따라서, A[j] - A[i]의 최대값을 구하기 위해 이중 for문을 사용하여 모든 경우의 수를 비교하면 된다.
- 개선 풀이
  - Time Complexity: $O(n)$
  - A[j] > A[i]인 경우에는 기존의 max값과 비교하여 최대값을 갱신하면 된다.
  - 그렇지 않을 경우에는 i를 j로 갱신한다.

def maxDifference(self, nums: List[int]) -> int:
    max_diff = -1
    min_val = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > min_val:
            max_diff = max(max_diff, nums[i] - min_val)
        else:
            min_val = nums[i]
    return max_diff

필요 없는 중간과정 생략하기

문제 링크
내 풀이
문제 요약
- n개의 섹터가 있는 원형 트랙이 주어졌을 때, 1번 섹터부터 n번 섹터까지 순서대로 방문한 횟수를 구하라.
풀이 요약
- 기존 풀이
  - n번째 섹터까지 방문한 횟수를 구하기 위해 n번째 섹터까지의 방문 횟수를 구하고, n번째 섹터까지의 방문 횟수를 구하는 과정을 반복한다.
- 개선 풀이
  - 어차피 한 바퀴를 돌 경우에 모든 섹터의 방문 횟수는 동일하다.
  - 따라서 1번 섹터부터 n번 섹터까지의 방문 횟수를 구하는 것은 필요 없는 중간과정이다.
  - 이 때문에 처음과 끝만 보면 된다.

def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
    start, end = rounds[0], rounds[-1]
    if start <= end:
        return list(range(start, end + 1))
    else:
        return list(range(1, end + 1)) + list(range(start, n + 1))

3개의 distinct한 subarray를 구하는 방법

문제 링크
내 풀이
문제 요약
- int array가 주어졌을 때, 3개의 distinct한 subarray를 구하고 각 subarray의 합이 최소가 되도록 하라.
- subarray는 연속된 요소들의 집합이다.
풀이 요약
- Time Complexity: $O(n^2)$
- 3개의 subarray를 구하기 위해 2중 for문을 사용하여 모든 경우의 수를 비교하면 된다.

```go func minCost(nums []int) int { n := len(nums)

minCost := math.MaxInt32
for i := 1; i < n - 1; i++ {
    for j := i + 1; j < n; j++ {
        cost := nums[0] + nums[i] + nums[j]
        minCost = min(minCost, cost)
    }
}
return minCost }

2024-05-12