ZeroOne

LeetCode : Sort an Array 문제를 풀다가 의문점이 생겼다.

제약조건은 다음과 같다.

• 1 <= nums.length <= 5 * 10^4
• -5 * 104 <= nums[i] <= 5 * 10^4

즉, nlog(n)으로 sorting해야하는 간단한 문제다.

근데 C++의 STL인 sort는 내부적으로 quick sort를 사용한다는데 어떻게 STL을 사용해 통과했을까?

quick sort는 최악의 경우 O(N^2)이다.

당연히, merge sort 같은 O(Nlog(N))을 사용해야할 줄 알았다.첫번째 풀이 merge sort다.

class Solution {
    public:
    void mergeSort(vector<int>& nums, int s, int e) {
        if (s != e) {
            int mid = (s+e)/2;
            mergeSort(nums, s, mid);
            mergeSort(nums, mid+1, e);
            merge(nums, s, mid, e);
        }
    }
    void merge(vector<int>& nums, int s, int m, int e) {
        int i = s;
        int j = m+1;
        int k = e;
        vector<int> tmp;
        while(i <= m && j <= e) {
            if (nums[i] < nums[j]) {
                tmp.push_back(nums[i++]);
            }
            else {
                tmp.push_back(nums[j++]);
            }
        }

        while (i <= m) {
            tmp.push_back(nums[i++]);
        }
        while (j <= e) {
            tmp.push_back(nums[j++]);
        }

        for (int i = s; i <= e; i++) {
            nums[i] = tmp[i-s];
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }
};

Runtime: 133 ms

두번째 풀이, sort STL이다.

class Solution {
    public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums;
    }
};

Runtime: 22 ms

성공했다. 심지어 시간도 훨씬 빠르다.

테스트 케이스도 1~50000의 정렬된 vector를 넣어봤다.

왜 되는 걸까?

내부적으로, sort는 단순히 quick sort가 아니라 최악의 경우를 대비한 로직이 있다고 한다.

따라서 문제풀때는 닥치고 sort쓰면 된다.

처음으로 leetcode hard 문제를 풀었다.

BFS와 Memoization을 적용한 풀이다.

초반엔 구조체 만들어서 풀었지만, tuple과 tie라는 STL을 적용하니 훨씬 깔끔해졌다.

그리고 {}를 이용해 데이터를 묶어주면 tuple, vector형식으로 자동 변환해준다.

시간복잡도는 m * n * k, 즉 40*40*1600이다. 

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        vector<vector<vector<int>>> dp;       
        dp.assign(41, vector<vector<int>>(41, vector<int>(1601, 0)));
        
        int ms = grid.size(); 
        int ns = grid[0].size();
        int rb, cb, kb;
        int cnt = 0;
        
        queue<tuple<int, int, int> > q;
        q.push({0, 0, k});
        
        while (!q.empty()) {
            tie(rb, cb, kb) = q.front();
            q.pop();
            int nb = dp[rb][cb][kb];
            
            if (rb == ms-1 && cb == ns-1) {
                continue;
            }
            if (rb < ms-1) {
                if (grid[rb+1][cb] == 1 && kb > 0) {
                    if (!dp[rb+1][cb][kb-1]) {
                        dp[rb+1][cb][kb-1] = nb+1;                     
                        q.push({rb+1, cb, kb-1});
                    }
                }
                else if (grid[rb+1][cb] == 0) {
                    if (!dp[rb+1][cb][kb]) {
                        dp[rb+1][cb][kb] = nb+1;
                        q.push({rb+1, cb, kb});
                    }
                }
            }
            if (cb < ns-1) {
                if (grid[rb][cb+1] == 1 && kb > 0) {
                    if (!dp[rb][cb+1][kb-1]) {
                        dp[rb][cb+1][kb-1] = nb+1;
                        q.push({rb, cb+1, kb-1});                        
                    }
                }
                else if (grid[rb][cb+1] == 0) {
                    if (!dp[rb][cb+1][kb]) {
                        dp[rb][cb+1][kb] = nb+1;
                        q.push({rb, cb+1, kb});                        
                    }
                }
            }
            if (rb > 0) {
                if (cb == 0)
                    continue;
                if (grid[rb-1][cb] == 1 && kb > 0) {
                    if (!dp[rb-1][cb][kb-1]) {
                        dp[rb-1][cb][kb-1] = nb+1;
                        q.push({rb-1, cb, kb-1});                        
                    }
                }
                else if (grid[rb-1][cb] == 0) {
                    if (!dp[rb-1][cb][kb]) {
                        dp[rb-1][cb][kb] = nb+1;
                        q.push({rb-1, cb, kb});
                    }
                }
            }
            if (cb > 0) {
                if (rb == 0)
                    continue;
                if (grid[rb][cb-1] == 1 && kb > 0) {
                    if (!dp[rb][cb-1][kb-1]) {
                        dp[rb][cb-1][kb-1] = nb+1;
                        q.push({rb, cb-1, kb-1});                        
                    }
                }
                else if (grid[rb][cb-1] == 0) {
                    if (!dp[rb][cb-1][kb]) {
                        dp[rb][cb-1][kb] = nb+1;
                        q.push({rb, cb-1, kb});                        
                    }
                }
            }
        }
        
        int mini = 1601;
        for (int i = 0; i < 1601; i++) {
            if (dp[ms-1][ns-1][i] != 0)
                mini = min(mini, dp[ms-1][ns-1][i]);
        }
        
        if (ms == 1 && ns == 1)
            return 0;
        
        if (mini != 1601)
            return mini;
        else
            return -1;
    }
};

2개의 데이터를 묶을 땐 pair를 사용하면 됐다.

그런데 leetcode hard단계를 풀다 보니 3개 묶는일이 많아지더라.

주로 tuple형태로 return되는 값을 받을 때 사용한다.

  ! c++ 11버전 이상에서만 사용가능하다

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

int main() {
    auto t = make_tuple(1, 2, 3);

    int x = get<0>(t);
    int y = get<1>(t);
    int z = get<2>(t);

    cout << x << ' ' << y << ' ' << z << '\n';    //1 2 3

    x = y = z = 0;
    cout << x << ' ' << y << ' ' << z << '\n';    //0 0 0
    
    tie(x, y, z) = t;
    cout << x << ' ' << y << ' ' << z << '\n';    //1 2 3

    x = y = z = 0;
    tie(x, y, ignore) = t;    //세번째 자리는 무시 : ignore
    cout << x << ' ' << y << ' ' << z << '\n';    //1 2 0

    return 0;
}

다음은 cpp reference url : https://en.cppreference.com/w/cpp/utility/tuple/tie

알고리즘 공부를 할때만 C++을 사용하다 보니 매번 헷갈려서 정리를 시작한다.

주로 Stack 이후에 배우지만, Stack보다 헷갈리는 함수가 많다.

특히, push_back이 아니라 push를 사용한다. (뒤로만 붙이기 때문)

그리고 emplace로 tuple같은 애들을 쉽게 넣을 수도 있더라. 꿀팁!

• front(): 큐에 있는 첫 번째 원소에 대한 참조를 반환한다. 큐가 const이면 const 참조를 반환한다. 큐가 비어 있을 때 반환되는 값은 정의되어 있지 않다.

• back(): 큐에 있는 마지막 원소에 대한 참조를 반환한다. 큐가 const이면 const 참조를 반환한다. 큐가 비어 있을 때 반환되는 값은 정의되어 있지 않다.

• push(const T& obj): obj의 복제본을 큐의 끝에 추가한다. 이 작업은 기반 컨테이너의 push_back() 멤버를 호출해서 수행된다.

• push(T&& obj): 큐의 끝에 obj를 이동해서 추가한다. 이 작업은 기반 컨테이너의 우측값 참조 매개변수 버전의 push_back() 멤버를 호출해서 수행된다.

• pop(): 큐에서 첫 번째 원소를 삭제한다.

• size(): 큐에 있는 원소의 개수를 반환한다.

• empty(): 큐에 원소가 하나도 없으면, 즉 비어 있으면 true를 반환한다.

• emplace(): emplace()에 전달된 인수로 T 생성자를 호출해 컨테이너 내부에 객체를 바로 생성하고 큐의 끝에 추가한다.

• swap(queue<T> &other_q): 현재 큐에 있는 원소들과 인수로 전달된 원소들을 교환한다. 인수는 현재 큐와 같은 타입으로 된 원소들을 담고 있어야 한다. queue 객체에 대해 같은 일을 하는 전역 함수 템플릿 swap() 같은 특수화도 있다.

C++ 11 부터 표준에 포함된 정규 표현식(regular expression)

• std::regex_match 를 이용해서 정규 표현식으로 전체 문자열 패턴 매칭하기.
• std::regex_search 를 이용해서 정규 표현식으로 문자열 검색하기
• std::regex_replace 를 이용해서 정규 표현식으로 문자열 치환하기

예제1 - 백준 2671 문제

#include <iostream>
#include <regex>
#include <string>

using namespace std;

string s;
regex re("(100+1+|01)+");

void solve() {
cin >> s;

if (regex_match(s, re)) {
cout << "SUBMARINE" << endl;
}
else {
cout << "NOISE" << endl; 
}
}

int main(void)
{
solve();

return 0;
}