99클럽 코테 스터디 33일차 TIL - 2195 Append K Integers With Minimal Sum

2195. Append K Integers With Minimal Sum / c++ / Medium / 8분+

문제 및 코드

#include <iostream>
class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        long long answer = 0;
        int addCount = 0;
        long long nextNum = 1;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] == nextNum)
            {
                nextNum++;
            }
            else
            {
                for (; nextNum < nums[i]; ++nextNum)
                {
                    answer += nextNum;
                    if (++addCount == k) break;
                }
                nextNum = nums[i] + 1;
            }
            if (addCount == k) break;
        }
        while (addCount++ < k)
        {
            answer += nextNum++;
        }

        return answer;
    }
};

접근 방식

정렬

1. k개의 중복되지 않은 양의 정수를 배열에 더할 때, 배열의 원소 합이 최소가 되는 정수들의 합을 구하는 문제였다.
2. 1번 조건을 다시 풀어서 적자면, 배열에 없는 원소를 가장 작은 순으로 k개 더한 합을 반환는 문제이다.
3. 배열을 정렬 후 순회하면서 nextNum (나올 것이라고 기대하는 수) 와 비교해준다.
4. 만약 nextNum < nums[i] 이라면, nextNum부터 nums[i]-1까지는 배열에 포함되지 않은 수가 된다.
5. 그러면 다시 순회를 돌면서 nextNum부터 nums[i]-1까지를 answer에 더해준다. (중간에 addCount를 측정해서 k와 같아지면 break)
6. 배열 순회가 끝난 후에도 addCount < k 이면, 다시 nextNum을 answer에 더하며 증가시켜준다. (배열의 원소들의 사잇값이 아닌, 배열의 끝 원소 이후에 추가되는 숫자들이다.)

생각해 볼 점

1. 배열 원소의 사잇값만 생각하고, 배열 순회 후에 다시 addCount == k 가 될 때까지, nextNum을 더해줄 생각을 못했다. (만약 문제가 어렵게 나왔다면 테스트 케이스에도 이 부분을 명시하지 않았을 것이다.) 항상 이런 엣지 케이스들을 쉽게 놓치는데, 문제를 읽을 때 좀 더 면밀하게 조건을 분석해야겠다.

해시태그

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