문제 링크

내 코드

111ms, 108.89MB

class Solution {
public:
    long long findScore(vector<int>& nums) {
        int n = {static_cast<int>(nums.size())};
        auto comp = [](const Data& d1, const Data& d2) {
            if(d1.value == d2.value) return d1.index > d2.index;
            return d1.value > d2.value;
        };

        priority_queue<Data, vector<Data>, decltype(comp)> pq(comp);
        for(int s{}; s < n; ++s) {
            pq.emplace(nums[s], s); // {value, index}
        }

        vector<int> dat(n, 0);
        long long answer{};
        while(!pq.empty()) {
            auto [value, index] = pq.top(); pq.pop();

            if(dat[index]) continue;
            answer += static_cast<long long>(value);

            dat[index] = 1;
            if(index - 1 >= 0) dat[index - 1] = 1;
            if(index + 1 < n) dat[index + 1] = 1;
        }
        return answer;
    }
private:
    struct Data {
        int value{}, index{};
        Data() = default;
        Data(int v, int i) : value{v}, index{i} {}
    };
};

Solution

Approach 1: Sorting

• 60ms, 98.87MB
• Complexity
  • Let $N$ be the size of nums.
  • Time Complexity: $O(N \cdot \log N)$
  • Space Complexity: $O(logN)$

class Solution {
public:
    long findScore(vector<int>& nums) {
        long ans = 0;
        vector<pair<int, int>> customSorted(nums.size());

        for (int i = 0; i < nums.size(); i++) {
            customSorted[i] = make_pair(nums[i], i);
        }

        sort(customSorted.begin(), customSorted.end());

        vector<bool> marked(nums.size(), false);

        for (int i = 0; i < nums.size(); i++) {
            int number = customSorted[i].first;
            int index = customSorted[i].second;
            if (!marked[index]) {
                ans += number;
                marked[index] = true;
                // mark adjacent elements if they exist
                if (index - 1 >= 0) {
                    marked[index - 1] = true;
                }
                if (index + 1 < nums.size()) {
                    marked[index + 1] = true;
                }
            }
        }

        return ans;
    }
};

GPT

이 코드는 주어진 배열 nums에 대해 특정 규칙에 따라 점수를 계산하는 과정을 구현한 것으로 보입니다. 전체적인 흐름은 다음과 같습니다:

1. (값, 인덱스) 쌍으로 재구성 및 정렬:

   vector<pair<int, int>> customSorted(nums.size());
   for (int i = 0; i < nums.size(); i++) {
       customSorted[i] = make_pair(nums[i], i);
   }
   sort(customSorted.begin(), customSorted.end());

   여기서 customSorted는 원래 배열 nums의 각 원소 값과 해당 인덱스를 담은 후, 값을 기준으로 오름차순 정렬한 벡터입니다.
   즉, (값, 인덱스) 형태로 가장 작은 값부터 차례대로 나열하게 됩니다.

2. marked 배열 준비:

   vector<bool> marked(nums.size(), false);

   marked는 각 인덱스가 이미 처리(선택 또는 제외)되었는지 여부를 나타냅니다. 초기에는 모두 false로, 아직 처리되지 않았음을 의미합니다.

3. 오름차순 순회하며 점수 계산:

   long ans = 0;
   
   for (int i = 0; i < nums.size(); i++) {
       int number = customSorted[i].first;
       int index = customSorted[i].second;
   
       // 아직 이 인덱스가 처리되지 않았다면 (marked가 false라면)
       if (!marked[index]) {
           ans += number;        // 해당 숫자를 점수에 더합니다.
           marked[index] = true; // 이 인덱스를 처리했다고 표시
   
           // 인접한 원소도 처리했다고 표시 (인접한 원소는 선택 불가하도록)
           if (index - 1 >= 0) {
               marked[index - 1] = true;
           }
           if (index + 1 < nums.size()) {
               marked[index + 1] = true;
           }
       }
   }

   • 정렬된 순서(가장 작은 값부터)로 순회하면서, 아직 처리되지 않은 인덱스를 발견하면 그 값을 점수(ans)에 더합니다.
   • 그 인덱스를 포함한 양 옆 인덱스를 marked = true로 만들어, 이후 다시 선택되지 않도록 합니다.
   • 이렇게 하면 한 번 어떤 원소를 선택하면 그 원소의 인접한 원소들은 선택 불가능해지는 규칙을 구현한 것으로 보입니다.

4. 결과 반환:

   return ans;

   모든 처리를 마친 뒤 ans를 반환합니다.

정리:

• 이 알고리즘은 “가장 작은 원소부터” 확인하면서, 그 원소가 아직 선택 가능하다면 점수에 반영하고, 그 원소와 인접 원소들을 선택 불가능하게 만드는 방식입니다.
• 결국 “값이 작은 순서대로 선택할 수 있을 때, 선택한 원소의 인접한 원소는 배제” 하는 규칙 하에 최대한 많은(또는 적절한) 원소를 선택하여 점수를 계산하는 로직입니다.
• 최종적으로 ans에는 선택된 원소들의 값 합이 들어가게 됩니다.

Approach 2: Heap

• 118ms, 105.80MB
• Complexity
  • Let $N$ be the size of nums.
  • Time Complexity: $O(N \cdot \log N)$
  • Space Complexity: $O(N)$

class Solution {
public:
    long long findScore(vector<int>& nums) {
        long long ans = 0;
        vector<bool> marked(nums.size());

        auto cmp = [](pair<int, int>& pair1, pair<int, int>& pair2) {
            if (pair1.first != pair2.first) return pair1.first > pair2.first;
            return pair1.second > pair2.second;
        };

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>
            heap(cmp);

        for (int i = 0; i < nums.size(); ++i) {
            heap.push(make_pair(nums[i], i));
        }

        while (!heap.empty()) {
            pair<int, int> element = heap.top();
            heap.pop();
            int number = element.first;
            int index = element.second;

            if (!marked[index]) {
                ans += number;
                marked[index] = true;

                // mark adjacent elements if they exist
                if (index - 1 >= 0) {
                    marked[index - 1] = true;
                }
                if (index + 1 < nums.size()) {
                    marked[index + 1] = true;
                }
            }
        }

        return ans;
    }
};

GPT

이 코드는 이전에 봤던 로직(값이 작은 원소부터 선택하고, 선택 시 그 원소와 양옆 인덱스를 “사용 불가”로 표시하여 최종 점수를 구하는 로직)을 우선순위 큐(priority_queue)를 활용하여 구현한 예시입니다. 핵심은 최소값부터 처리하기 위해 커스텀 비교 함수를 사용한 최소 힙처럼 동작하는 priority_queue를 만드는 것입니다.

동작 과정 상세 설명:

1. marked 배열 초기화:

   vector<bool> marked(nums.size());

   각 인덱스가 처리되었는지 여부를 추적하는 marked 배열입니다. 초기에는 모두 false로, 아직 처리되지 않은 상태를 의미합니다.

2. 커스텀 비교 함수(cmp) 정의:

   auto cmp = [](pair<int, int>& pair1, pair<int, int>& pair2) {
       if (pair1.first != pair2.first) return pair1.first > pair2.first;
       return pair1.second > pair2.second;
   };

   • pair<int,int>는 (값, 인덱스) 형태를 의미합니다.
   • 이 비교 함수는 우선 값(first)을 비교하고, 값이 같다면 인덱스(second)를 비교합니다.
   • return pair1.first > pair2.first;는 pair1가 pair2보다 “더 큰 값”을 가지면 true를 반환합니다.

   priority_queue는 내부적으로 이 cmp 함수로 원소의 우선순위를 정합니다. C++에서 priority_queue는 기본적으로 최대 힙 구조인데, 이 cmp를 통해 가장 작은 값을 top에 오도록(즉, min-heap처럼) 동작하게 만들 수 있습니다.

   정리하자면, cmp 함수로 인해 priority_queue의 top은 항상 “가장 작은 값, 그 중에서도 인덱스가 작은 원소”가 위치하게 됩니다.

3. priority_queue 초기화:

   priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> heap(cmp);
   for (int i = 0; i < nums.size(); ++i) {
       heap.push(make_pair(nums[i], i));
   }

   nums의 모든 원소 (값, 인덱스)를 힙에 넣습니다. 이제 힙의 top에는 가장 작은 값(그리고 값이 같으면 더 작은 인덱스)이 위치합니다.

4. 힙을 이용한 처리가 메인 로직:

   long long ans = 0;
   
   while (!heap.empty()) {
       auto element = heap.top();
       heap.pop();
       int number = element.first;
       int index = element.second;
   
       if (!marked[index]) {
           ans += number;
           marked[index] = true;
   
           // 인접 원소도 marked 처리
           if (index - 1 >= 0) {
               marked[index - 1] = true;
           }
           if (index + 1 < nums.size()) {
               marked[index + 1] = true;
           }
       }
   }

   • 힙에서 가장 작은 값의 원소를 꺼냅니다.

   • 해당 인덱스가 아직 처리되지 않았다면(!marked[index]):

     • 점수 ans에 그 원소의 값을 더합니다.
     • 해당 인덱스와 양 옆 인덱스를 marked = true로 설정하여 향후 재선택 불가하게 합니다.

   • 이미 marked된 인덱스라면 무시하고 다음 힙 원소를 처리합니다.

   이 로직은 값이 작은 것부터 순서대로 처리하기 때문에, 이전 정렬 기반 풀이와 동일한 결과를 얻게 됩니다.

5. 결과 반환:

   return ans;

정리:

• 이 코드는 priority_queue를 최소 힙처럼 사용하기 위해 커스텀 비교 함수를 사용하였고, 값이 작은 원소부터 선택하는 과정을 힙에서 pop하는 것으로 구현했습니다.
• 선택한 원소는 ans에 더하고, 그 원소와 양 옆을 marked 처리하여 나중에 같은 범위에서 고려하지 못하도록 합니다.
• 결국, “가장 작은 값부터 선택하면서 인접한 원소는 배제”하는 규칙을 힙 자료구조를 통해 효율적으로 구현한 코드입니다.

Approach 3: Sliding Window

• 2ms, 92.16MB
• Complexity
  • Let $N$ be the size of nums.
  • Time Complexity: $O(N)$
  • Space Complexity: $O(1)$

class Solution {
public:
    long long findScore(vector<int>& nums) {
        long long ans = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            int currentStart = i;
            while (i + 1 < nums.size() && nums[i + 1] < nums[i]) {
                i++;
            }
            for (int currentIndex = i; currentIndex >= currentStart;
                 currentIndex -= 2) {
                ans += nums[currentIndex];
            }
        }
        return ans;
    }
};

GPT

이 코드는 주어진 nums 배열을 특정한 규칙에 따라 값을 누적하여 ans를 계산합니다. 다만, 코드 자체만 봐서는 원 문제의 의도가 분명치 않기 때문에, 코드가 실제로 수행하는 동작을 단계별로 해석해보겠습니다.

코드 동작 과정:

1. 2칸씩 건너뛰며 진행 (i += 2):
   바깥쪽 for문은 i를 0부터 시작하여 매번 2씩 증가시킵니다.

   for (int i = 0; i < nums.size(); i += 2) {
       int currentStart = i;
       ...
   }

   이는 i가 처음엔 0, 그 다음엔 2, 4, 6 … 와 같이 짝수 인덱스에서 어떤 처리를 시작한다는 의미입니다.

2. 감소하는 패턴 확장 (while 루프):

   while (i + 1 < nums.size() && nums[i + 1] < nums[i]) {
       i++;
   }

   여기서는 현재 위치 i에서 시작한 뒤, 다음 원소(nums[i+1])가 현재 원소(nums[i])보다 작으면 i를 1씩 더 증가시키며 전진합니다.

   이 루프가 끝나면, [currentStart ... i] 구간은 currentStart에서 시작해서 i까지 진행하는 동안 “인접한 다음 원소가 전 원소보다 작아지는” 조건을 만족하는 최대 구간이 됩니다. 다시 말해, currentStart로 시작해서 가능한 한 길게 “내림차순으로 이어지는” 부분을 찾습니다.

3. 찾은 구간에서 2칸씩 뒤로 가며 합산:

   for (int currentIndex = i; currentIndex >= currentStart; currentIndex -= 2) {
       ans += nums[currentIndex];
   }

   이제 i는 내림차순 패턴의 끝 지점입니다. 이 지점부터 currentStart까지 거꾸로 가면서(뒤로 이동) 인덱스를 2씩 감소시키며 nums[currentIndex] 값을 ans에 더합니다.

   즉, 발견한 내림차순 부분 구간의 끝에서 시작하여, 두 칸씩 건너뛰며 해당 구간의 일부 원소들을 합산하는 것입니다.

정리하면,

• 매 짝수 인덱스(i)에서 시작:
  currentStart = i로 설정.

• 내림차순으로 이어지는 최대 구간 탐색:
  다음 원소가 계속 더 작다면 i++하며 구간을 확장.

• 확장된 구간에 대해, 끝에서 시작해 2칸 간격으로 요소 합산:
  [currentStart ... i] 구간에서 i부터 currentStart까지 currentIndex -= 2로 내려가며 nums[currentIndex]를 합산.

결과적으로 이 코드는 배열을 짝수 인덱스 단위로 시작하는 내림차순 연속 구간들을 찾고, 각 구간 끝에서부터 2칸씩 건너뛰며 해당 원소들을 ans에 더한 뒤, 최종적으로 ans를 반환하는 로직을 구현하고 있습니다.

원 문제의 맥락이 없어 의도를 정확히 파악하기는 어렵지만, 코드가 수행하는 로직은 위와 같이 해석할 수 있습니다.

---

해당 코드도 LeetCode의 “Find Score of an Array After Marking All Elements” 문제에 대한 해설(또는 해설을 바탕으로 한 다른 접근) 중 하나로 보입니다. 다만 이 코드는 이전에 설명한 정렬 후 최소값을 차례로 선택하는 직접적인 방식과는 다르게, 문제를 풀어나가는 또 다른 관점 또는 패턴 기반 접근을 보여주는 것으로 추측됩니다. 문제 의도를 이미 알고 있다면, 이 코드가 어떤 수학적 규칙성이나 배열의 특정 패턴을 이용해 답을 구하려 한다고 해석할 수 있습니다.

이해를 위한 추론:

1. 문제 복습:
   문제에서는 매 단계에서 “표시되지 않은 원소들 중 최솟값”을 골라 점수에 더하고, 그 인덱스와 양옆을 표시하는 과정을 반복합니다. 결국 선택되는 원소들은 특정한 패턴(가장 작은 값들을 중심으로 양옆이 ‘사용 불가’ 처리되는 패턴)을 형성하게 됩니다.

2. 코드 분석:

   for (int i = 0; i < nums.size(); i += 2) {
       int currentStart = i;
       while (i + 1 < nums.size() && nums[i + 1] < nums[i]) {
           i++;
       }
       for (int currentIndex = i; currentIndex >= currentStart; currentIndex -= 2) {
           ans += nums[currentIndex];
       }
   }

   • 바깥쪽 for문: i를 0부터 시작해서 2씩 증가.
   • while문: 현재 위치 i에서 시작해 바로 다음 원소가 더 작다면 i를 1 증가. 이는 currentStart에서 시작하는 “내림차순” 패턴을 가능한 한 길게 찾는 과정으로 보입니다.
   • 내림차순 패턴을 찾은 뒤, 그 구간 [currentStart ... i]를 뒤에서부터 2칸씩 건너뛰며 ans에 더합니다.

   이 로직은 겉보기에는 문제의 “최솟값 선택 및 표시” 과정과 직접적으로 대응하지 않는 것처럼 보이지만, 다음과 같은 추론이 가능합니다:

   • 문제를 충분히 분석하면, “최소값을 선택하고 양옆을 막아나가는” 과정을 모두 마친 뒤 최종적으로 선택된 원소들의 패턴이 특정 규칙을 갖게 되는데, 이 코드는 그 규칙을 단축적으로 활용한 것으로 추정할 수 있습니다.
   • 즉, 실제로 매번 최소를 찾아 표시하는 시뮬레이션을 하지 않고, 배열의 구조적 특징(예: 짝수 인덱스 시작, 내림차순 구간 식별, 그 구간 내에서 특정 위치의 원소들을 선택)을 통해 동일한 결과를 빠르게 계산하는 ‘수학적’ 접근일 수 있습니다.

3. 정리:

   • 이 코드 또한 같은 문제를 풀기 위한 해설/접근 방식 중 하나입니다.
   • 직접 최소값을 찾고 표시하는 시뮬레이션 대신, 배열을 순회하며 특정 패턴(짝수 인덱스에서 시작하는 내림차순 구간) 안에서 특정 인덱스들만 골라내어 점수에 반영하는 방식으로 결과적으로 문제 정답과 동일한 점수를 얻는 것으로 보입니다.
   • 문제의 공식 해설과 다르게, 이 코드는 문제의 해법을 다른 관점에서 단순화하거나 최적화한 결과일 수 있습니다. 결국 “표시 과정”의 결과로 생기는 패턴을 사전에 파악하여, 별도의 마킹/정렬 없이도 최종 결과를 도출하는 식의 우회 전략인 것으로 이해할 수 있습니다.

요약하자면, 이 코드는 같은 문제(Find Score of an Array After Marking All Elements)의 결과를 얻기 위한 또 다른 수단으로, 문제의 점수를 계산하는 데 필요한 패턴을 알아내어 그 규칙을 코드로 옮긴 해설 코드로 해석할 수 있습니다.