1. 배열 중복제거 투포인터

배열에서 중복 제거하는건데 새 배열 선언하면 안됨
-> 투포인터 사용해서 중복 제거함

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

출처 : 리트코드

2. 배열에서 부분 합 찾기 투포인터

배열 안에서 연속되는 숫자의 합이 m인 개수 찾기
-> 투포인터 사용해서 합이 m보다 작으면 늘리고, 합이 m보다 크면 줄이는 방식

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> v;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
    
    int cnt = 0;
    int s = 0;
    int e = 0;
    int sum = 0;
    
    while(1){
        if(e == n+1)
            break;
        if(sum > m){
            sum -= v[s];
            s++;
        }else if(sum < m){
            sum += v[e];
            e++;
        }else{
            cnt++;
            sum += v[e];
            sum -= v[s];
            s++;
            e++;
        }
    }
    cout << cnt << "\n";
    return 0;
    
}

출처 : 백준 2003 수들의 합 2

3. 배열에서 두 값의 합이 target이 되는거 찾기

배열이 주어지고 배열안의 두 원소의 합이 target이 되는것을 찾는 문제
-> 그냥 바로 푸는게 2중 for문을 통해 다 비교하는거(브루트포스) : O(n^2)
-> 해쉬 맵 사용하면 O(n)으로 해결 가능 : 해쉬 맵은 삽입, 삭제, 참조 모두 O(1), 그냥 맵은 O(logn)

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

출처 : 리트코드 two sum

4. Palindrome 수 판단

주어진 숫자가 palindrome 수 인지 판단하는 문제
-> palindrome 은 거꾸로 읽어도 같은 숫자
-> 처음에는 문자열로 변환해서 풀었음
-> 숫자 거꾸로 구해서 일치 여부 판단하여 풀 수도 있음
-> 이거 더 발전시키면 예를들어 12321이 있으면 맨 뒤 두자리만 보고 판단 가능
-> 이런 경우 123이랑 12이니까 123/10 한거랑 비교하면 됨

class Solution {
public:
    bool isPalindrome(int x) {
        
        if(x < 0 || (x % 10 == 0 && x != 0))
            return false;

        int revertedNumber = 0;
        
        while(x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber/10;
        
        /*if(x<0)
            return false;
        string str = to_string(x);
        for(int i=0;i<str.size()/2;i++){
            if(str[i] != str[str.size()-1-i])
                return false;
        }
        return true;*/
    }
};

출처 : 리트코드 palindrome number

5. 타겟 위치 찾기

배열 안에 타겟이 들어갈 위치를 찾는거
-> 시간복잡도 O(logn)으로 해야함
-> binary search 사용

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;
        while(start <= end){
            int mid = (start + end)/2;
            if(nums[mid] == target)
                return mid;
            if(target > nums[mid]){
                start = mid+1;
            }else{
                end = mid-1;
            }
        }
        return start;
    }
};

출처 : 리트코드 Search insert Position

6. 부분배열의 최대 합 구하기

배열 안의 연속된 부분 배열 중 최대 합을 구하는 문제
-> 접근방법 세가지 있음
-> O(n^2) : 그냥 브루트포스
-> O(nlogn) : 분할정복
-> O(n) : dp
dp로 푼거

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int tmp = nums[0];
        int m = nums[0];
        for(int i=1;i<nums.size();i++){
            tmp = max(nums[i],tmp+nums[i]);
            m = max(tmp,m);
        }
        return m;
    }
};

출처 : 리트코드 Maximum Subarray

7. 트리의 최소 깊이 구하기

binary tree의 최소 깊이 구하는 문제
-> 재귀 사용해서 해결 가능
-> 왼쪽이 null 이면 오른쪽으로 가야함
-> 마찬가지로 오른쪽이 null 이면 왼쪽으로 가야함

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        
        if(root->left == NULL)
            return minDepth(root->right) + 1;
        
        if(root->right == NULL)
            return minDepth(root->left) + 1;
        
        return 1+min(minDepth(root->left),minDepth(root->right));
    }
    
};

출처 : 리트코드 Minimum Depth of Binary tree

8. 연결리스트의 사이클 찾기

연결리스트에 사이클이 존재하면 true, 없으면 false 반환 문제
-> 해쉬 맵 사용해서 맵 안에 값 존재하면 true 아니면 false 반환하면 됨
-> 아니면 fast and slow 알고리즘을 통해 풀 수 있음
-> fast를 slow 보다 두배 빠르게 진행시켜서 fast가 tail에 도달하면 slow가 가리키는 값은 리스트의 중간이다 라는 알고리즘인데
-> 여기서는 사이클 유무 판단하는 거라 slow랑 fast가 같아지면 true인 거임

//unordered_map<ListNode*,bool> m;
class Solution {
public:
    bool hasCycle(ListNode *head) {
        /*if(head == NULL)
            return false;
        if(m[head] == true)
            return true;
        m[head] = true;
        return hasCycle(head->next);*/
        
        ListNode *fast = head;
        ListNode *slow = head;
        while(1){
            if(fast == NULL || fast->next == NULL)
                break;
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

출처 리트코드 Linked List Cycle

9. 소수 개수 구하기

소수의 개수를 구하는 문제이다
-> 에라토스테네스의 체를 활용하면 됨
-> 그 수가 소수가 아니라면 그 수의 배수들을 다 지워주는 식
-> 근데 이거를 n까지 다 할 필요 없이 현재수의 제곱이 n보다 작을 때 까지만 하면 됨(이건 몰랐던 사실)
-> 이렇게 하는 이유는 i보다 작은 k에 대해서 i*k는 k의 배수를 지울 때 이미 지워 졌으므로 i^2부터 하면 된다.

class Solution {
public:
    int countPrimes(int n) {
        vector<int> prime(n+1);
        int cnt = 0;
        for(int i=2;i*i<n;i++){
            if(prime[i] == 0){
                for(int j=i*i;j<n;j+=i){
                    prime[j] = 1;
                }
            }
        }
        
        for(int i=2;i<n;i++){
            if(prime[i] == 0)
                cnt++;   
        }
        
        return cnt;
    }
};

출처 리트코드 Count Primes

10. 정렬된 두 배열 합치기

정렬되어 있는 두 배열을 합쳐서 정렬된 상태를 유지하는 문제이다.
-> void 형식이므로 매개변수를 통해 반환해야 한다.
-> 반환할 매개변수의 크기는 두 배열의 원소 개수를 합친 크기만큼 할당되어 있다.

• 처음 생각
  투포인터 느낌으로 각자 배열 인덱스 가리키는 변수 선언해서 다른 배열에 저장 후 저장할 변수에 할당 해 준다.
  -> 시간, 공간 복잡도 모두 O(m+n)
• 두번째 생각
  접근 법은 같은데 매개변수의 맨 뒤부터 큰수부터 저장하면 됨
  -> 새 배열 할당 안해줘도 되므로 공간복잡도는 O(1)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int tmp = m + n -1;
        int a = m-1;
        int b = n-1;
        while(1){
            if(tmp == -1)
                break;
            if(a == -1){
                nums1[tmp] = nums2[b];
                b--;
                tmp--;
                continue;
            }else if(b == -1){
                nums1[tmp] = nums1[a];
                a--;
                tmp--;
                continue;
            }
            
            if(nums1[a] > nums2[b]){
                nums1[tmp] = nums1[a];
                a--;
                tmp--;
            }else if(nums1[a] <= nums2[b]){
                nums1[tmp] = nums2[b];
                b--;
                tmp--;
            }   
        }
        return;
        
        
        // 새 배열에 저장 하는 방법
        /*int a = 0;
        int b = 0;
        vector<int> v;
        while(1){
            if(a == m && b == n)
                break;
            
            if(a == m){
                v.push_back(nums2[b]);
                b++;
                continue;
            }else if(b == n){
                v.push_back(nums1[a]);
                a++;
                continue;
            }
            
            if(nums1[a] > nums2[b]){
                v.push_back(nums2[b]);
                b++;
            }else{
                v.push_back(nums1[a]);
                a++;
            }
        }
        nums1 = v;
        return;*/
    }
};

출처 리트코드 Merge Sorted Array

11. 스택 두개로 큐 구현

-> 스택 두개로 큐의 동작을 구현
-> in 스택 push 구현
-> out 스택 pop을 위한 저장 공간으로 구현
-> pop할 때 만약 out 스택이 비어 있으면 in 스택의 모든 원소들 옮겨야함
-> pop할 때 만약 out 스택이 남아 있으면 그냥 해당 스택 pop 하면 됨
-> 구조체 써서 해서 함수 호출할 때 인자로 큐 넘겨 줘야 하고, 변경 내용 적용하려면 & 연산 사용해야함

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

typedef struct Queue{
    stack<int> in_s;
    stack<int> out_s;
}queue;

void q_push(queue &q, int n){
    cout << "push : " << n << "\n";
    q.in_s.push(n);
}

int q_pop(queue &q){
    if(q.out_s.empty() && q.in_s.empty())
        return -1;

    if(q.out_s.empty()){
        while(!q.in_s.empty())
        {
            q.out_s.push(q.in_s.top());
            q.in_s.pop();
        }
    }

    int n = q.out_s.top();
    q.out_s.pop();
    return n;
}

int main() {
    queue q;
    for(int i=0;i<10;i++)
        q_push(q,i);

    cout << q_pop(q) << "\n";
    cout << q_pop(q) << "\n";
    cout << q_pop(q) << "\n";
    q_push(q,10);
    q_push(q,11);
    q_push(q,12);
    while(1){
        int n = q_pop(q);
        if(n == -1)
            break;
        cout << n << "\n";
    }
    return 0;
}

12. 제곱 판단

-> num 이 주어졌을 때 이 수가 제곱인지 아닌지 판단하는 문제
-> 사이즈 그리 안커서 그냥 linear 하게 탐색했음
-> 근데 시간 더 줄이려면 binary search 사용하면됨
-> 그냥 linear 탐색은 무조건 binary로 시간 줄일 수 있다고 생각하면 될듯

class Solution {
public:
    bool isPerfectSquare(int num) {
        
        long long int start = 1;
        long long int end = num;
        
        while(start <= end){
            long long int mid = (start + end)/2;
        
            if(mid*mid == num)
                return true;
            
            if(mid*mid > num)
                end = mid-1;
            else
                start = mid+1;
        }
        
        return false;
        
        
        
        /*long i = 1;   
        while(i*i<num){
            i++;
        }
        if(i*i == num)
            return true;
        else
            return false;*/
    }
};

출처 리트코드 Valid Perfect Square

13. 두 bst 합치기

-> 두개의 binary serach tree를 합쳐서 원소를 오름차순으로 정렬하는 문제
-> binary search tree는 순회 방식이 중위 순회이기 때문에 왼쪽 끝 노드 - 가운데 - 오른쪽 순으로 순회 해야한다.

class Solution {
public:
    void inorder(vector<int> &v, TreeNode* root){
        if(root == NULL)
            return;
        inorder(v,root->left);
        v.push_back(root->val);
        inorder(v,root->right);
        return;
    }
        
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> v1;
        vector<int> v2;
        inorder(v1,root1);
        inorder(v2,root2);
        
        vector<int> ans;
        int i=0;
        int j=0;
        while(i!=v1.size() || j!=v2.size()){
            if(i == v1.size()){
                ans.push_back(v2[j]);
                j++;
                continue;
            }
            if(j == v2.size()){
                ans.push_back(v1[i]);
                i++;
                continue;
            }
            
            if(v1[i] <= v2[j]){
                ans.push_back(v1[i]);
                    i++;
            }else{
                ans.push_back(v2[j]);
                j++;
            }
        }
        return ans;
    }
};

출처 리트코드 All Elements in Two Binary Search Tree

14. 제곱근 찾기

-> 수가 주어지면 그 수의 제곱근 찾는 문제, 정수 부분만 반환
-> 12번과 비슷하게 접근함
-> 처음에는 그냥 linear하게 접근하였음
-> 이분탐색 활용하면 훨씬 더 빠르게 찾기 가능(시간 거의 8배 차이나는것 확인 가능)

/*class Solution { // 선형 탐색
public:
    int mySqrt(int x) {
        for(long long i=1;;i++){
            if(i*i > x){
                return i-1;
            }
        }
    }
};*/

class Solution { // 이분탐색
public:
    int mySqrt(int x) {
        long long start = 1;
        long long end = x;
        while(start <= end){
            long long int mid = (start + end) / 2;
            if(mid*mid > x){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return start - 1;
    }
};

출처 리트코드 sqrt(x)

15. 트리 경로 합 구하기

-> 트리의 루트 노드 부터 리프노드 까지 합과 목표하는 숫자가 같은 경우가 있는지 판단하는 문제이다.
-> 트리를 전부 순회해야 하므로 dfs를 사용할 수 있다.(재귀)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root)
            return false;
        targetSum -= root->val;
        if(!root->right && !root->left)
            return targetSum == 0;
        
        return hasPathSum(root->right, targetSum) || hasPathSum(root->left, targetSum);
    }
};




/*class Solution {
public:
    bool dfs(TreeNode* node, int targetSum, int prev){
        int cur = node->val + prev;
        if(node->left == NULL && node->right == NULL){
            if(cur == targetSum)
                return true;
            else
                return false;
        }
        
        if(node->left != NULL){
            bool flag = dfs(node->left, targetSum, cur);
            if(flag == true)
                return true;
        }
        if(node->right != NULL){
            bool flag = dfs(node->right, targetSum, cur);
            if(flag == true)
                return true;
        }
        return false;
    }
    
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL)
            return false;
        int cur = root->val;
        if(root->left == NULL && root->right == NULL){
            if(cur == targetSum)
                return true;
            else
                return false;
        }
        if(root->left != NULL){
            if(dfs(root->left, targetSum, cur))
                return true;
        }
        if(root->right != NULL){
            if(dfs(root->right, targetSum, cur))
                return true;
        }
        return false;
    }
};*/

출처 리트코드 Path Sum

16. happy number 찾기

-> happy number

-> 처음에는 그냥 set에 저장해서 지금 판단하려는 숫자가 있는지 확인함
-> fast and slow 알고리즘 적용해서 문제 품

class Solution { // slow and fast 사용
public:    
    int cal(int n){
        int cnt = 0;
        while(1){
            cnt += (n%10)*(n%10);
            n /= 10;
            if(n == 0)
                break;
        }
        return cnt;
    }
    
    bool isHappy(int n) {
        int slow = n;
        int fast = cal(n);
        while(slow != fast){
            slow = cal(slow);
            fast = cal(cal(fast));
            if(fast == 1 || slow == 1)
                return true;
        }
        if(slow == 1)
            return true;
        return false;
    }
};



/*#include <set> // set 사용
class Solution {
public:
    
    bool isHappy(int n) {
        int tmp = n;
        set<int> s;
        while(1){
            int cnt = 0;
            if(tmp == 1)
                return true;
            if(s.find(tmp) != s.end())
                return false;
            s.insert(tmp);
            while(1){
                cnt += (tmp%10)*(tmp%10);
                tmp /= 10;
                if(tmp == 0){
                    tmp = cnt;
                    break;
                }
            }
        }
    }
};*/

출처 리트코드 Happy Number