[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 사용자들 보다는 느리다.
문제 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++은 리턴 타입을 정했으면 어떻게든 리턴 해줘야 한다.