(C++) - leetcode 2007번 : Find Original Array From Doubled Array

https://leetcode.com/contest/biweekly-contest-61/problems/find-original-array-from-doubled-array/

Account Login - LeetCode

greedy? 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

나온 수를 세줄 일차원 배열 countNum, 수가 사용되었는지의 여부를 저장할 isUsed 배열, 정답을 반환할 vector ans를 선언합니다.

 

 1. countNum을 0으로 초기화해줍니다.

 

 2. 기존 배열 값들의 2배가 함께 저장된 배열이 input으로 들어오기 때문에 doubled array가 되려면 changed의 원소 수는 무조건 짝수여야 합니다. 만약 짝수가 아니라면 바로 ans를 반환합니다.

 

 3. changed배열을 오름차순으로 정렬합니다.

 

 4. changed의 각 원소를 index로 해 countNum[원소]++ 해줍니다.

 

📔 풀이과정

예제의 경우 [1, 3, 4, 2, 6, 8]를 오름차순으로 정렬한다면 [1, 2, 3, 4, 6, 8]이 됩니다. 여기서 가장 왼쪽에 있는 값 1부터 시작해 2배인 원소들을 짝을 지어보면 [1, 2], [2, 4], [3, 6], [4, 8]의 형태로 중복하여 짝지어지게 됩니다. 중복해서 짝지으면 안됩니다. 때문에 중복되지 않도록 짝을 왼쪽부터 되는대로 짝을 짓게 된다면 그럴싸하게 될 것 같습니다. 하지만 중복된 값에 대해서도 적절히 짝을 지어야 합니다. 이미 짝을 진 원소를 또 짝짓는 것을 알기 위해 countNum에 저장된 값을 사용합니다.0에서 changed.size() - 1까지 loop를 돌며 다음을 시행합니다. 1. int c를 선언 후 changed[i]값을 저장합니다.

 

 2. 현재 자기 자신이 이미 짝지어졌기 때문에 짝지을 필요가 없다면 continue를 해줍니다.

 

 3. 자신의 2배한 값이 없다면 답이 없으므로 빈 vector를 return합니다.

 

 4. 자신, 자신을 2배한 값이 있다면 수를 사용해준뒤 ans에 c값을 push_back해줍니다.

 

📔 정답출력

정답 vector ans를 반환해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int countNum[200001];
class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        memset(countNum,0,sizeof(countNum));

        vector <int> ans;

        if(changed.size() % 2) return ans;

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

        for(auto c : changed) countNum[c]++;

        for(int i = 0; i < changed.size(); i++){
            int c = changed[i];
            if(!countNum[c]) continue;
            if(!countNum[c*2]) return vector<int>();
            countNum[c]--, countNum[c*2]--;
            ans.push_back(c);
        }
        return ans;
    }
};