[리트코드] 2058 - Find the Minimum and Maximum Number of Nodes Between Critical Points

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

Medium

---

A critical point in a linked list is defined as either a local maxima or a local minima.

A node is a local maxima if the current node has a value strictly greater than the previous node and the next node.

A node is a local minima if the current node has a value strictly smaller than the previous node and the next node.

Note that a node can only be a local maxima/minima if there exists both a previous node and a next node.

Given a linked list head, return an array of length 2 containing [minDistance, maxDistance] where minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return [-1, -1].

 

Example 1:

Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points in [3,1].

Example 2:

Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:
- [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

Example 3:

Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points:
- [1,3,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,3,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.

 

Constraints:

• The number of nodes in the list is in the range [2, 105].
• 1 <= Node.val <= 105

분류

연결 리스트

---

문제 풀이

다음은 주어진 알고리즘 문제에 대한 풀이 설명입니다.

---

문제 분석

이 문제는 단일 연결 리스트(Singly Linked List)에서 "임계점(Critical Point)"을 찾아, 임계점들 사이의 최소 및 최대 거리를 계산하는 것을 요구합니다.

• 임계점의 정의:

  • 지역 최대값(local maxima): 현재 노드의 값이 이전 노드의 값보다 크고, 다음 노드의 값보다도 클 때.
  • 지역 최소값(local minima): 현재 노드의 값이 이전 노드의 값보다 작고, 다음 노드의 값보다도 작을 때.
  • 주의: 첫 번째 노드와 마지막 노드는 이전 노드 또는 다음 노드가 없으므로 임계점이 될 수 없습니다. 즉, 임계점이 되려면 반드시 이전 노드와 다음 노드가 모두 존재해야 합니다.

• 거리의 정의: 두 임계점 사이의 거리는 그들의 0-기반 인덱스(위치) 차이로 정의됩니다.

• 요구사항:

  • [minDistance, maxDistance] 형태의 배열을 반환합니다.
  • minDistance: 두 어떤 서로 다른 임계점 사이의 최소 거리.
  • maxDistance: 두 어떤 서로 다른 임계점 사이의 최대 거리 (이는 첫 번째 임계점과 마지막 임계점 사이의 거리가 됩니다).
  • 만약 임계점이 2개 미만이라면, [-1, -1]을 반환합니다.

• 입력: 연결 리스트의 head 노드.

• 제약 조건: 리스트의 노드 수는 2개 이상 10^5개 이하. 노드 값은 1 이상 10^5 이하.

접근 방법

문제를 해결하기 위해 연결 리스트를 한 번만 순회하는 접근 방식을 사용합니다. 각 노드를 방문하면서 임계점인지 확인하고, 임계점이라면 그 노드의 인덱스(위치)를 기록합니다.

1. 임계점 식별: 임계점을 식별하려면 현재 노드의 값, 이전 노드의 값, 그리고 다음 노드의 값을 알아야 합니다. 이를 위해 리스트를 순회하면서 세 개의 "슬라이딩 윈도우"처럼 값을 추적합니다.
2. 인덱스 추적: 각 노드의 0-기반 인덱스를 추적하는 카운터 변수를 유지합니다. 임계점이 발견되면 해당 임계점의 인덱스를 저장합니다.
3. 최소 거리 계산: 임계점이 발견될 때마다, 직전에 발견된 임계점과의 거리를 계산하고, 이 값이 현재까지의 최소 거리인지 확인하여 업데이트합니다. 이를 위해 min_a 변수와 tmp (가장 최근 임계점 인덱스) 변수를 사용합니다.
4. 최대 거리 계산: 모든 임계점의 인덱스를 저장하는 리스트(result)를 유지합니다. 모든 순회가 끝난 후, 이 리스트의 첫 번째 임계점과 마지막 임계점의 인덱스 차이가 최대 거리가 됩니다.
5. 예외 처리: 만약 result 리스트에 2개 미만의 임계점이 저장되었다면, [-1, -1]을 반환합니다.

이 방법은 연결 리스트를 한 번만 순회하므로 효율적이며, 추가적인 정렬이나 복잡한 자료구조 없이 문제를 해결할 수 있습니다.

구현 설명

주어진 코드는 다음 단계로 나누어 설명할 수 있습니다.

1. 변수 초기화 및 첫 두 노드 처리

• bb_num, b_num 초기화: bb_num은 '이전의 이전 노드'의 값을, b_num은 '이전 노드'의 값을 저장합니다. head.val이 '현재 노드'의 값이 됩니다. 이 세 변수를 통해 임계점 판별에 필요한 세 개의 연속된 노드 값을 유지합니다. 초기에는 None으로 설정됩니다.
• result 리스트 초기화: 발견된 모든 임계점의 인덱스를 저장할 빈 리스트입니다.
• cnt 초기화: 현재 순회 중인 노드의 0-기반 인덱스를 추적하는 카운터입니다. 0으로 시작합니다.
• min_a 초기화: 최소 거리를 저장할 변수로, float("inf") (무한대)로 초기화하여 어떤 실제 거리 값도 이보다 작게 만듭니다.
• tmp 초기화: 가장 최근에 발견된 임계점의 인덱스를 저장할 변수입니다. 초기에는 None입니다.
• 첫 두 노드 건너뛰기: while head: 루프 안에서, bb_num이 None일 때는 head.val을 bb_num에 할당하고, b_num이 None일 때는 head.val을 b_num에 할당합니다. 이 두 노드는 임계점이 될 수 없으므로, 값을 저장하고 다음 노드로 넘어갑니다. 이 단계를 통해 임계점 검사를 위한 최소 세 개의 노드 값을 확보합니다.

2. 임계점 판별 및 인덱스 기록 (세 번째 노드부터)

• else 블록은 bb_num과 b_num에 유효한 값이 할당된, 즉 세 번째 노드부터 실행됩니다.
• 임계점 조건 확인: if (b_num > bb_num and b_num > head.val) or (b_num < bb_num and b_num < head.val):
  • 이 조건은 b_num (이전 노드)이 bb_num (이전의 이전 노드)과 head.val (현재 노드) 사이에서 지역 최대값 또는 지역 최소값인지 확인합니다.
  • 여기서 중요한 점은 b_num의 노드가 임계점이라는 것이고, 이 노드의 인덱스는 cnt - 1입니다.
• 최소 거리 업데이트:
  • if not tmp:: 만약 현재 발견된 임계점이 첫 번째 임계점이라면, 그 인덱스(cnt - 1)를 tmp에 저장합니다.
  • else:: 이미 이전에 임계점이 발견된 경우, 현재 임계점(cnt - 1)과 이전 임계점(tmp) 사이의 거리를 계산 ((cnt - 1) - tmp)하여 min_a를 업데이트합니다. 이후 tmp를 현재 임계점의 인덱스(cnt - 1)로 업데이트합니다.
• 모든 임계점 인덱스 저장: result.append(cnt - 1)을 통해 현재 발견된 임계점의 인덱스 (cnt - 1)를 result 리스트에 추가합니다.

3. 슬라이딩 윈도우 이동 및 순회 진행

• 임계점 확인이 끝난 후, 다음 노드를 검사하기 위해 '슬라이딩 윈도우'를 한 칸 이동시킵니다.
  • bb_num = b_num: 이전 노드의 값이 '이전의 이전 노드'의 값으로 옮겨집니다.
  • b_num = head.val: 현재 노드의 값이 '이전 노드'의 값으로 옮겨집니다.
• head = head.next: head 포인터를 다음 노드로 이동시킵니다.
• cnt += 1: 노드 인덱스 카운터를 증가시킵니다.

4. 결과 반환

• while 루프가 끝나면 모든 노드를 순회하고 임계점들을 처리한 상태입니다.
• 임계점 개수 확인: if len(result) < 2:
  • result 리스트에 임계점이 2개 미만으로 저장되어 있다면, 문제의 요구사항에 따라 [-1, -1]을 반환합니다.
• 최종 결과 반환: return [min_a, result[-1]-result[0]]
  • min_a는 위에서 계산된 최소 거리를 나타냅니다.
  • result[-1] - result[0]는 result 리스트의 마지막 임계점 인덱스에서 첫 번째 임계점 인덱스를 뺀 값으로, 이는 연결 리스트 내의 최대 거리가 됩니다 (왜냐하면 result에 저장된 인덱스들은 항상 오름차순이기 때문입니다).

⏱복잡도 분석

• 시간 복잡도: O(N)

  • 코드는 연결 리스트의 각 노드를 정확히 한 번만 방문합니다.
  • 각 노드에 대해 상수 시간(O(1))의 연산(값 비교, 할당, 리스트 추가)을 수행합니다.
  • 따라서 전체 시간 복잡도는 연결 리스트의 노드 수 N에 비례합니다.

• 공간 복잡도: O(N)

  • result 리스트는 발견된 모든 임계점의 인덱스를 저장합니다. 최악의 경우, 연결 리스트의 절반에 가까운 노드들이 임계점이 될 수 있습니다 (예: [1, 5, 1, 5, 1, 5, ...]).
  • 이 경우 result 리스트의 크기는 O(N)이 될 수 있습니다.
  • bb_num, b_num, cnt, min_a, tmp 등의 다른 변수들은 상수 공간(O(1))을 사용합니다.
  • 따라서 전체 공간 복잡도는 O(N)입니다.

핵심 포인트

1. 세 노드의 슬라이딩 윈도우: 임계점을 판별하기 위해 현재 노드, 이전 노드, 이전의 이전 노드 등 세 노드의 값을 동시에 추적하는 '슬라이딩 윈도우' 기법을 사용합니다 (bb_num, b_num, head.val). 이를 통해 연결 리스트를 한 번만 순회하면서 효율적으로 임계점 조건을 확인할 수 있습니다.
2. 정확한 인덱스 추적: 거리를 계산하기 위해서는 노드의 0-기반 인덱스를 정확하게 추적하는 것이 중요합니다. cnt 변수를 사용하여 현재 head가 가리키는 노드의 인덱스를 유지하고, 임계점으로 판별된 b_num 노드의 실제 인덱스(cnt - 1)를 정확히 기록합니다.
3. 최소/최대 거리의 효율적 계산:
   • 최소 거리: 임계점을 발견할 때마다 직전 임계점과의 거리를 즉시 계산하고 min_a를 업데이트하는 '온더플라이(on-the-fly)' 방식으로 O(1) 시간에 최소 거리를 찾습니다.
   • 최대 거리: 모든 임계점의 인덱스를 result 리스트에 순서대로 저장한 후, 마지막 임계점 인덱스에서 첫 번째 임계점 인덱스를 빼는 방식으로 O(1) 시간에 최대 거리를 계산합니다. 이 방식은 인덱스들이 이미 정렬되어 있기 때문에 가능합니다.

풀이 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        bb_num = None
        b_num = None

        result = []
        cnt = 0
        min_a = float("inf")
        tmp = None

        while head:
            if not bb_num:
                bb_num = head.val
            elif not b_num:
                b_num = head.val
            else:
                if (b_num > bb_num and b_num > head.val) or (b_num < bb_num and b_num < head.val):
                    if not tmp:
                        tmp = cnt

                    else:
                        min_a = min(min_a, cnt-tmp)
                        tmp = cnt

                    result.append(cnt)

                bb_num = b_num
                b_num = head.val

            head = head.next
            cnt += 1

        if len(result) < 2:
            return [-1,-1]

        return [min_a, result[-1]-result[0]]