[C++/LeetCode/Top Interview Questions]Array

생각보다 문제가 빨리 풀려서 카테고리 별로 포스팅을 올리는게 나을 것 같다. 풀리긴 풀리는데 계속 아쉬운 마음이 든다. 파이썬처럼 C++도 C++만의 장점을 살릴 수 있는 방법이 있을 텐데, 파이썬 코드를 C++로 바꾼 것처럼 풀고 있다. 심지어 파이썬이 아니니 파이썬의 장점도 죽는다😂. 근데 풀다보니 C++도 파이썬만큼은 아니지만 꽤 편한 것 같다. 

 

문제 5. Single Number

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int answer = 0;
        sort(nums.begin(), nums.end());
        for (int i=0; i<nums.size(); i++) {
            answer ^= nums[i];
        }
        return answer;
    }
};

 

이 문제는 XOR을 사용하면 쉽게 풀리는 문제다. 

 

 

문제 6.   Intersection of Two Arrays II

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        
        vector<int> intersection;
        int n = nums1.size(), m = nums2.size();
        int i = 0, j = 0;
        
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        
        while (i<n && j<m) {
            if (nums1[i] == nums2[j]) {
                intersection.push_back(nums1[i]);
                i += 1;
                j += 1;
            } 
            else if (nums1[i] < nums2[j]){
                i += 1;   
            }
            else if (nums1[i] > nums2[j]){
                j += 1;
            }
        }
     return intersection;   
    }
};

 

중복 원소를 없애면 안되니까 set 의 intersection을 사용하지 못하는 문제다. 기존에 파이썬으로 풀었던 것 보다는 빠르지만, 다른 cpp 사용자들 보다는 느리다.

 

3월 10일 파이썬 풀이보다 8배나 빠르다

다른 C++ 사용자들은 메모리를 희생시켜서 속도를 얻었나 싶은 결과

 

문제 7.   Plus One

 

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for (int i = n-1; i > -1; i--){
            if (digits[i] == 9) {
                digits[i] = 0;
            }
            else {
                digits[i]++;
                return digits;
            }
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

 

배열이 이어져 있는 숫자라고 생각하고 1을 더했을 때의 답을 배열로 리턴하는 문제다.

• 배열이 [1, 2, 4] 라면 124고 이에 1을 더하면 125가 되니까 답은 [1, 2, 5]가 된다.
• 만약 배열이 [1, 2, 9] 라면 129고 이에 1을 더하면 130이 되니까 답은 [1, 3, 0]이 된다. 그래서 for문에서 digits[i] == 9면 digits[i]를 0이 되게 하고, 윗 자리에 1을 더하게 했다. 
• 만약 배열이 [9, 9, 9]일 경우 for loop 내에서 return을 하지 않으니 배열은 [0, 0, 0]이 된다. 그래서 for loop 내에서 return이 되지 않을 경우, digits 의 처음 위치에 1을 삽입하게 했다.

 

파이썬에서는 배열의 인덱스로 접근했는데, C++에서는 포인터로 접근한다. 처음에 digits.insert(0, 1); 이라고 했다가 컴파일 에러가 발생했다. 주의해야겠다.

 

 

문제 8. Move Zeroes

 

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                for (int j = i; j < n; j++) {
                    if (nums[j] != 0) {
                        swap(nums[i], nums[j]);
                        break;
                    }
                }
            }
        }
    }
};

 

풀긴 풀었는데 메모리도 런타임도 하위 10%다. 세상에 나와서는 안되는 코드다. 통과는 했지만 개선 방법을 고민해봐야겠다. 다들 O(N)으로 풀었던데 O(N^2)니까 당연한거겠지만... 왜 되는건지 이해가 안된다.

 

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                int j;
                for (j = i; j < n; j++) {
                    if (nums[j] != 0) {
                        swap(nums[i], nums[j]);
                        break;
                    }
                }
                if (j == n) break;
            }
        }
    }
};

 

시간은 많이 개선 못했는데 메모리는 개선했다. 시간은 이중 포문을 사용하는 한 답이 없을 듯 하다. 

 

 

문제 9. Two Sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> dict;
        for (int i = 0; i < nums.size(); i++) {
            int res = target - nums[i];
            dict.insert(make_pair(res, i));
        }
        
        
        vector<int> answer;
        for (int i = 0; i < nums.size(); i++) {
            if (dict.count(nums[i]) && dict[nums[i]]!=i) {
                answer.push_back(i);
                answer.push_back(dict[nums[i]]);
                break;
            }
        }
        return answer;
    }
};

 

C++에서 처음으로 해쉬맵을 사용한 문제다. 사용 방법은 파이썬이랑 비슷한 듯 하다. 해쉬맵을 선언하는 방법이랑, 해쉬맵에 (키, 값)을 넣을 때 make_pair(key, value) 함수를 사용한다는 것을 기억해야겠다.

 

파이썬은 함수를 선언할 때 리턴 타입을 명시적으로 정하지 않아서 리턴을 제대로 처리하지 않은 것으로 컴파일 에러가 나는 일은 없었는데, C++은 리턴 타입을 정했으면 어떻게든 리턴 해줘야 한다.