Sho1007

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

1 minute read

2551. Put Marbles in Bags / c++ / Hard / 1시간+

문제 및 코드

#include <iostream>
#include <algorithm>

vector<int> costVector;

class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {

        costVector = vector<int>(weights.size()-1);

        for (int i = 0; i < weights.size() - 1; ++i)
        {
            costVector[i] = weights[i] + weights[i+1];
        }

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

        long long maxCost = 0;

        for (int i = 0; i < k-1; ++i)
        {
            maxCost += costVector[costVector.size() - 1 - i];
        }
        long long minCost = 0;
        for (int i = 0; i < k-1; ++i)
        {
            minCost += costVector[i];   
        }

        return maxCost - minCost;
    }
};

접근 방식

정렬

  1. 가장 단순하게 모든 구간을 잘라봤다. (전수조사, 백트래킹) -> 시간 초과
  2. 시간을 단축할 수 있는 방법을 찾아보려 했지만 결국 찾지 못했고, 힌트를 봤다.
  3. 힌트에서 나눠지는 부분의 앞과 뒤를 사용해라고 나와 있었다.
  4. pair<int,int> 를 원소로 가지는 우선순위 큐를 선언하여 끊어질 수 있는 부분을 모두 넣었다.
  5. 이러면 크거나 작은 한가지의 기준으로 정렬된 값을 꺼낼 수 있지만 여기선 최소값과 최대값 두가지의 기준이 필요했고, 기존 방법으로는 정렬의 반대 순서로 꺼내는게 번거로웠다.
  6. 다시 생각해보니 굳이 우선순위 큐를 쓰지 않고, 벡터에 다 넣은 다음 정렬하면 앞뒤로 꺼낼 수 있었다.
  7. 다른 분들의 풀이를 보니 또 굳이 pair<int,int> 로 나눠지는 부분을 받지 않고, 어차피 더해질 거 그냥 int 로 처음부터 더한 값을 원소로 받으면 된다는 점을 깨달았다.
  8. 마지막으로 항상 maxSum - minSum을 반환하기 때문에, 맨 앞과 맨 뒤 원소는 maxSum과 minSum에 모두 포함되어 결국 상쇄되는 값이었다.
  9. 이런 최적화 과정을 통해 최종 식이 (내림차순 정렬의 k-1개의 원소의 합) - (오름차순 정렬의 k-1개의 원소의 합) 이라는 점을 깨달았다.

생각해 볼 점

  1. 리트코드는 힌트와 풀이 방법을 제공해준다는 점이 신기했다.
  2. 힌트도 단계별로 나눠져 있어서 하다가 도저히 안되겠을 때 차례로 한 개씩 열어볼 수 있다는 점이 좋았다.
  3. 이해하고 나니 단순 정렬 문제였는데, 풀이 과정을 유추해 내는 것이 너무 어려웠다.
  4. 마치 구현 방법을 식으로 나타내고 그 식을 최적화하여 최종 계산식을 뽑아내는 느낌이었다.
  5. 내가 부족한 부분이 문제 전체를 도식화하여 해결하는 능력이라는 것을 다시 한번 깨달을 수 있었다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

You may also enjoy