weekly-contest-187

https://leetcode.com/contest/weekly-contest-187/

 

1번 문제 - 1436. Destination City

https://leetcode.com/contest/weekly-contest-187/problems/destination-city/

문자열 배열 [["B","C"],["D","B"],["C","A"]] 일때

D->B->C->A 로 경로를 나타낼 수 있다. 마지막 최종 경로인 A 를 출력 하는 문제이다.

시작점과 끝점은 1 번만 나오게 된다.

class Solution {
public:
    // 마지막은 항상 뒤에 있음으로 
    string destCity(vector<vector<string>> & paths) {
        map<string, pair<int,int>> m;

        for (int i = 0; i < paths.size(); i++) {
            for (int j = 0; j < paths[i].size(); j++) {
                if (j == 0) {
                    m[paths[i][j]];
                    m[paths[i][j]].first = 1;
                }

                if (j == 1) {
                    m[paths[i][j]];
                    m[paths[i][j]].second = 1;
                }
            }
        }

        string sol;
        for (auto a : m) {
            pair<int, int> p = a.second;
            if (p.first == 0 && p.second == 1) {
                sol = a.first;
                break;
            }
        }
        return sol;
    }
};

 

2번 문제 - 1437. Check If All 1's Are at Least Length K Places Away

https://leetcode.com/contest/weekly-contest-187/problems/check-if-all-1s-are-at-least-length-k-places-away/

1 과 1 사이에 거리가 k 보다 작다면 false

class Solution {
public:
    

    bool kLengthApart(vector<int>& nums, int k) {

        vector<int> arr;
        int size = nums.size();
        int i = 0;
        while (size != i) {

            if (nums[i] == 0) {
                int cand = 0;
                for (int j = i; j < nums.size(); j++) {
                    if (nums[j] == 0) {
                        cand++;
                    }
                    else {
                        break;
                    }
                }
                arr.push_back(cand);
                i += cand;
            }
            else {
                i++;
            }

        }
        for (int i = 0; i<arr.size(); i++) {
            if (arr[i] < k)
                return false;
        }
        return true;
    }
};

 

3번 문제 - 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

class Solution {
public:
    int longestSubarray(vector<int>& A, int limit) {
        int i = 0, j;
        multiset<int> m;
        for (j = 0; j < A.size(); ++j) {
            m.insert(A[j]);
            if (*m.rbegin() - *m.begin() > limit)
                m.erase(m.find(A[i++]));
        }
        return j - i;
    }
};