[ leetcode 문제풀이 ] 3Sum

https://leetcode.com/problems/3sum/

3Sum - LeetCode

(3Sum 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< 3Sum 문제 설명 >

 

3Sum 문제는 다음과 같다.

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

 

주어진 정수 배열 nums에 대해 더해서 0이 되는 모든 세 원소의 순서쌍을 리턴하여라(세 원소는 서로 다른 index로부터 옴). solution 집합이 중복된 순서쌍을 가져서는 안된다.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 0 ≤ nums.length ≤ 3000,  -10^5 ≤ nums[i] ≤ 10^5 이다.

 

 

 

---

< 3Sum 문제 접근 >

 

맨 처음 생각한 방법은 nums에서 조합할 수 있는 두 원소의 순서쌍((nums[i], nums[j]) 단, i<j)에 대해 더해서 0을 만족하는 nums[k]를 unordered_map(hash table 자료구조)을 이용해 탐색하고자 하였다. 작성한 코드는 다음과 같다. (Cpp 사용)

 

#include <algorithm>
#include <unordered_map>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> ans;
    if(nums.size() < 3) return ans;
       
    unordered_map<int,vector<int>> numsMap;
    for(int i=0;i<n;i++)
        numsMap[nums[i]].push_back(i);
      
    for(int firstElemIndex = 0; firstElemIndex < n; firstElemIndex++)
        for(int secondElemIndex = firstElemIndex+1; secondElemIndex < n; secondElemIndex++){
            if(nums[firstElemIndex] == 0 && nums[secondElemIndex] == 0) continue;
              
            auto thirdElem = numsMap.find(-nums[firstElemIndex]-nums[secondElemIndex]);
            if(thirdElem != numsMap.end() && thirdElem -> second.back() > secondElemIndex){
                vector<int> temp = {nums[firstElemIndex], nums[secondElemIndex], thirdElem -> first};
                ans.push_back(temp);
            }  
        }
    return ans;
}

 

이렇게 작성한 코드의 문제점은 중복된 순서쌍을 생성한다는 점이다. 

 

Input :      [-1,0,1,2,-1,-4]

Output:    [[-1,0,1],[-1,2,-1],[0,1,-1]]

Expected: [[-1,-1,-2],[-1,0,1]]

 

firstElemIndex와 secondElemIndex 선정에는 중복된 2개 원소의 순서쌍을 생성하지 않았으나, thirdElem의 선택이 중복된 순서쌍 생성에 기여하였다. 이를 해결하기 위해 순서쌍을 다 구한 후 정렬해주고자 하였다.

 

#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        if(nums.size() < 3) return ans;
        
        unordered_map<int,vector<int>> numsMap;
        for(int i=0;i<n;i++)
            numsMap[nums[i]].push_back(i);
        
        for(int firstElemIndex = 0; firstElemIndex < n; firstElemIndex++)
            for(int secondElemIndex = firstElemIndex+1; secondElemIndex < n; secondElemIndex++){                
                auto thirdElem = numsMap.find(-nums[firstElemIndex]-nums[secondElemIndex]);
                if(thirdElem != numsMap.end() && thirdElem -> second.back() > secondElemIndex){
                    vector<int> temp = {nums[firstElemIndex], nums[secondElemIndex], thirdElem -> first};
                    sort(temp.begin(), temp.end());
                    ans.push_back(temp);
                }  
            }
        
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        
        return ans;
    }   
}

 

이 경우 답은 제대로 출력되나 time limit exceed를 나타냈다. 

위 코드는 Input: [0,0,0,0,0,0,0, ... ,0,0,0,0] 과 같은 경우에 특히 취약했는데 이 경우 서로 다른 nums 원소 순서쌍만 구하면 되는 목표에 반해 불필요하게 많은 범위를 탐색하게 되기 때문이다. 따라서 firstElem과 secondElem의 탐색도 hash table을 사용해야 유리하다고 판단하였다. 

 

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> ans;
    if(nums.size() < 3) return ans;
        
    unordered_map<int,vector<int>> numsMap;
    for(int i=0;i<n;i++)
        numsMap[nums[i]].push_back(i);
        
    for(auto firstElem = numsMap.begin(); firstElem != numsMap.end(); firstElem++)
        for(auto secondElem = firstElem; secondElem != numsMap.end(); secondElem++){
            if(firstElem != secondElem || firstElem->second.size() != 1){
                if(firstElem->first == 0 && secondElem->first == 0){
                    if(firstElem ->second.size() > 2) 
                        ans.push_back({0,0,0});
                }
                else{
                    auto thirdElem = numsMap.find(-(firstElem->first) -(secondElem->first));
                    if(thirdElem != numsMap.end() && (firstElem != thirdElem || firstElem -> second.size() != 1)
                      && (secondElem != thirdElem || secondElem -> second.size() != 1)){
                        vector<int> temp = {firstElem->first, secondElem->first, thirdElem->first};
                        sort(temp.begin(), temp.end());
                        ans.push_back(temp);
                    }
                }
            }
        }
        
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
        
    return ans;
} // runtime 312 ms(faster than 18.97 %), memory usage 31.7 MB(less than 12.63 %)

 

hash table을 사용해 nums의 index로 탐색하는 것이 아니라 nums의 value로 바로 탐색하므로 중복해서 탐색하는 순서쌍의 개수를 줄일 수 있었다. 아쉬운 점은 고려해야 하는 조건문이 너무 복잡하고 여전히 중복해서 탐색하는 case가 존재한다는 것이다. 

 

이 문제를 해결하기 위해 선택한 firstElem, secondElem의 값을 가지는 index를 제거하는 과정(pop_back)을 거쳤으며firstElem ≤ secondElem ≤ thirdElem 이라는 조건을 강제하여 중복되는 case 자체를 제거하였다. 

 

#include <unordered_map>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> ans;
    if(nums.size() < 3) return ans;
        
    unordered_map<int,vector<int>> numsMap;
    for(int i=0;i<n;i++)
        numsMap[nums[i]].push_back(i);
        
    for(auto firstElem = numsMap.begin(); firstElem != numsMap.end(); firstElem++){
        int temp1 = firstElem->second.back();
        firstElem->second.pop_back();
        
        for(auto secondElem = numsMap.begin(); secondElem != numsMap.end(); secondElem++){
            if(!secondElem->second.empty() && firstElem->first <= secondElem->first){
                int temp2 = secondElem->second.back();
                secondElem->second.pop_back();
                
                auto thirdElem = numsMap.find(-(firstElem->first) -(secondElem->first));
                if(thirdElem != numsMap.end() && !thirdElem->second.empty() && secondElem->first <= thirdElem->first){
                    vector<int> temp = {firstElem->first, secondElem->first, thirdElem->first};
                    ans.push_back(temp);
                }
                secondElem->second.push_back(temp2);
            }
        }
        firstElem->second.push_back(temp1);
    }
        
    return ans;
} // runtime 562 ms(faster than 14.07 %), memory usage 22.6 MB(less than 32.86 %)

 

다 구현을 했는데 runtime과 memory usage가 좋지 못해서 좀 찜찜하다.

vector에 대한 호출, 삽입, 삭제가 많이 일어나서 느린 것 같기도 하고... 정확한 원인은 잘 모르겠다.

 

다음에 기회가 되면 코드를 손봐야겠다.