Sho1007

MMORPG 클라이언트 개발자 지망생

2 minute read

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points / c++ / Medium / 30분

문제 및 코드

문제 링크

class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        vector<int> result;
        int pos = 1;
        int minDistance = 100'001;
        ListNode* prev = nullptr;
        ListNode* current = head;

        while (current != nullptr)
        {
            if (prev != nullptr && current->next != nullptr)
            {
                if ((current->val > prev->val && current->val > current->next->val) ||
                (current->val < prev->val && current->val < current->next->val))
                {
                    result.push_back(pos);
                    int resultSize = result.size();
                    if (resultSize > 1)
                    {
                        int currentDistance = result[resultSize-1] - result[resultSize-2];
                        if (currentDistance < minDistance)
                        {
                            minDistance = currentDistance;
                        }
                    }
                }
            }

            prev = current;
            current = current->next;
            pos++;
        }

        if (minDistance == 100'001)
        {
            result = {-1, -1};
        }
        else
        {
            result = {minDistance, result.back() - result.front()};
        }
        
        return result;
    }
};

접근 방식

자료 구조 / 링크드 리스트

  1. Critical Point 들의 거리 중 { 최소 거리, 최대 거리} 를 반환하는 문제였다.
  2. 여기서 Critical Point 란, 링크드 리스트의 노드 중
    1. 이전 원소, 현재 원소, 다음 원소가 모두 존재 하고 (nullptr이 아니고)
    2. 현재 원소의 값이 이전 원소와 다음 원소의 값보다 {크거나/작은} 노드이다.
      (ex. 1 3 2 중 3은 critical point, 5 2 4 여기서 2는 critical point)
  3. 우선 모든 critical point들의 거리를 vector result에 저장했다.
    1. 싱글 링크드 리스트였으므로, ListNode* prev를 만들어서 이전 값을 저장해줬다. (초기값 nullptr)
    2. prev, current, next (current->next)가 모두 nullptr 가 아닌지 체크
    3. current->val이 prev->val, next->val 보다 {크거나, 작은지} 체크
    4. 위의 조건에 만족한다면 현재 pos를 result에 삽입
  4. 내가 생각한 결과는 최대거리는 제일 처음 발견한 critical point와 가장 마지막에 발견한 critical point 의 거리였다.
  5. 그리고 모든 critical point가 pos가 증가하는 순서대로 정렬되어 result에 들어오기 때문에, 최소 거리는 인접한 노드와의 거리 중 최소값이라고 생각했다.
    1. 그래서 3번 로직을 수행하면서, result의 크기가 2 이상일 때 (원소가 2개 이상은 있어야 둘 사이의 거리를 구할 수 있으므로)
    2. 가장 마지막 값 (현재 critical point)와 그 바로 전 값 (이전 critical point)의 거리를 currentDistance로 구해줬다.
    3. 그리고 currentDistance가 minDistance보다 작다면 갱신해줬다. (minDistance의 초기값은 100’001로 잡았다. 원소가 최대 100’000개 있을 수 있으므로 최대 100’001은 못넘기 때문에)
  6. result를 {minDistance, result.back() - result.front()} 로 갱신하고 반환
  7. 해결

생각해 볼 점

  1. 처음에 계속 첫 번째 critical point의 위치가 2번씩 들어가서 최소 거리가 0으로 잡히는 오류가 생겼다.
  2. 알고보니 while 문 안에서 critical point의 조건을 검사하고, 조건에 맞지 않으면 early return을 해줬었는데, 링크드 리스트를 다음 노드로 진행시키고 pos를 증가시키는 구문이 그 아래에 존재해서, 같은 노드를 한번 더 검사했던 것이었다.
  3. early return이 깊이를 증가시키지 않아서 좋은 점도 있지만, 흐름을 명확히 신경써야 한다는 단점도 존재한다는걸 다시금 깨달을 수 있었다.

You may also enjoy