C++ 코테 준비.md

Array

1

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        return nums.size();
    }
};

2

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int before = nums.size();
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        return (before != nums.size());
    }
};

3

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        
        int n = nums.size();
        vector<int> temp(n);
        for (int i=0; i<n; i++){
            temp[(i+k)%n] = nums[i];
        }
        for (int i=0; i<n; i++){
            nums[i] = temp[i];
        }
        
    }
};

4

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 1; i < prices.size(); i++){
            profit += max(prices[i]-prices[i-1], 0);
        }
        return profit;
        
    }
};

문제 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++은 리턴 타입을 정했으면 어떻게든 리턴 해줘야 한다.

String

문제 1. Reverse String

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

vector에는 reverse(start, end) 함수가 있으니까 사용하면 된다. 

문제 2. Reverse Integer

class Solution {
public:
    int reverse(int x) {
        string str_x = to_string(x);
        string rev_str_x;
        for (int i=str_x.size()-1; i>-1; i--) rev_str_x += str_x[i];
        
        long long res = stoll(rev_str_x);
        if (x < 0) res *= -1;
        return (res<INT_MIN || res>INT_MAX) ? 0 : res;
    }
};

stoi(), stol(), stoll()에 대해 알 수 있었다. stoi는 string to integer, stol은 string to long, stoll은 string to long long의 약자다. 예전에 파이썬에서 이진 검색 알고리즘을 공부하다가 자료형의 최댓값 부분을 인상깊게 본 적이 있다. 이진 검색 알고리즘에서 중간 값을 구할 때 보통 (left+right)//2 를 하는데 이렇게 하면 자료형이 최댓값을 초과해 overflow를 발생시키게 된다. 따라서 mid = left + (right - left) // 2 이렇게 구현해야 한다. 이 문제도 파이썬이었으면 정수 오버플로우 에러를 겪지 않았을거다. 

• 문자열 변수를 선언할 때는 string, 숫자 변수를 문자열로 바꿀때는 to_string()함수를 사용하면 된다.
• 문자열 더하기(+)를 허용한다.
• 정수 최대값, 최소값 INT_MAX, INT_MIN
• stoi(), stol(), stoll()

문제 3.First Unique Character in a String

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> dict;
        for (int i=0; i<s.size();i++){
            if (dict.count(s.at(i)) > 0) dict[s.at(i)] += 1;
            else dict.insert(make_pair(s.at(i), 1));
        }
        for (int i=0; i<s.size(); i++){
            if (dict[s.at(i)] == 1) return i;
        }
        return -1;
    }
};

unordered_map 선언할 때 <string, int> 로 해서 계속 오류났었다.  자나깨나 자료형 조심

문제 4. Valid Anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

문제 5. Valid Palindrome

class Solution {
public:
    bool isPalindrome(string s) {
        
        string a, b;
        for (int i = 0; i<s.size(); i++) if (isalnum(s[i])) a += tolower(s[i]);
        b = a;
        reverse(b.begin(), b.end());
        return a == b;
    }
};

string 끼리 = 연산자를 사용한 복사는 깊은 복사다. alpha+numeric 인지 확인은 isalnum(), alpha인지 확인은 isalpha(), lower case로는 변경할 때는 **tolower()**을 사용한다. 숫자인지 확인은 **isdigit()**을 사용한다. 

문제 6. String to Integer (atoi)

atoi 부분만

class Solution {
public:
    int myAtoi(string res) {
        int sign = 1;
        int i = 0;
        if (res[0] == '-') {
            sign = -1;
            i ++;
        }
        
        int ans = 0;
        for (; res[i]!='\0';++i) ans = ans *10 + res[i] -'0';
        ans *= sign;
        
        if (ans >= INT_MAX) return INT_MAX;
        if (ans <= INT_MIN) return INT_MIN;
        return ans;
    }
};

전체 답

class Solution {
public:
  int myAtoi(string str) {
        if (str.empty()) return 0;
        int i = 0, sign = 1, n = str.size();
      
        while (i + 1 < str.size() && isspace(str[i])) ++i;      
        if (str[i] == '-') {
            sign *= -1; 
            i++;
        }
        else if (str[i] == '+') i++;
      
        long res = 0;
        while (i < n) {
            if (isdigit(str[i])) res = 10 * res + str[i++] - '0';
            else return res * sign;
            
            if (res > INT_MAX) return sign == -1 ? INT_MIN : INT_MAX;
        }
        return res * sign;
    }
};

문제 7.  Implement strStr()

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            if (j == n) {
                return i;
            }
        }
        return -1;
    }
};

문제 9. Longest Common Prefix

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix="";
        if(strs.size()==0) return prefix;
        
        for(int j=0; j<strs[0].size(); j++){
            int i=1;
            for(; i<strs.size() && strs[i].size()>j; i++){
                if(strs[i][j]!=strs[0][j]) return prefix;
            }
            if(i==strs.size()) prefix+=strs[0][j];
        }
        return prefix;
    }
};

ETC

숫자의 각 자릿수 구하기

int main(){
    int number = 12345678;
    while (number != 0)  cout << number%10 << endl;
    return 0;
}

strcpy 구현

void _strcpy(char *dest, char *src){
    while (*src != '\0') *(dest++) = *(src++);
    *(dest) = '\0';
}

strlen 구현

void _strlen(char *input){
    int i=0;
    while (input[i] != '\0') i++;
    return i;
}

swap 구현

void swap(int *a, int *b){
    int tmp = *b;
    *b = *a;
    *a = tmp;
}

swap(&a, &b);

multi-thread and mutex

#include <iostream>
#include <thread>
using namespace std;

void func1(){
    cout<<"thread1"<<endl;
}

void func2(){
    cout<<"thread2"<<endl;
}

int main(void){
    thread t1(func1);
    thread t2(func2);
    
    t1.join();
    t2.join();
}

mutex는 mutex mtx; mtx.lock(); mtx.unlock(); 해서 사용함(한 프로세스만 들어갈 수 있도록함).