2. 자료구조

[JiaYoon]

• 풀이

  • https://leetcode.com/problems/valid-parentheses/
  • https://leetcode.com/problems/find-median-from-data-stream/

• 문제

  1. 준기, 영륜 : https://leetcode.com/problems/score-of-parentheses/
  2. 중환, 재호 : https://leetcode.com/problems/task-scheduler/
  3. 지아, 승호 : https://leetcode.com/problems/sliding-window-median/

[JiaYoon]

c++ 문법 참고 사이트 http://soen.kr/

[JiaYoon]

class Solution {
public:
    bool isValid(string s) {

        stack<int> stack;

        size_t size = s.length();
        for(int i = 0; i < size; i++){
            if(isOpen(s[i])){
                stack.push(s[i]);
            }else{
                if(!stack.empty() && stack.top() == getOpen(s[i])){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }

        if(stack.empty()) return true;
        else return false;
    }

    bool isOpen(char c){
        if(c == '(') return true;
        if(c == '{') return true;
        if(c == '[') return true;
        return false;
    }
    char getOpen(char c){
        if(c == ')') return '(';
        if(c == '}') return '{';
        if(c == ']') return '[';

        return '(';
    }
};

[scsc3313]

480 Sliding Window Median

• multiset은 중복 값을 삽입이 가능한 set으로 insert 하면 자동 정렬이 됨.

class Solution {
public:
    multiset <double> windowMultiSet;
    double findMedian(double remove, double add) {
        windowMultiSet.insert(add);
        windowMultiSet.erase(windowMultiSet.find(remove));
        int n = windowMultiSet.size();
        if (n % 2 != 0) {
            return *next(windowMultiSet.begin(), n/2);
        } else {
            double a = *next(windowMultiSet.begin(), n/2 - 1); 
            double b = *next(windowMultiSet.begin(), n/2);    
            return (a + b) / 2;
        }
    }

    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        vector <double> result;
        for(int i=0; i < k; i++) {
            windowMultiSet.insert(nums[i]);
        }
        result.push_back(findMedian(0, 0));
        for(int i=0; i<nums.size() - k; i++) {
            result.push_back(findMedian(nums[i], nums[i+k]));
        }
        return result;
    }
};

[Leeyoungryun]

856. Score of Parentheses

class Solution {
public:
    int scoreOfParentheses(string S) {
    int cnt = 1;
    int result = 0;
    bool isDoubleOpen = false;

    size_t size = S.length();

    for (int i=0 ; i<size ; i++) {
        if (isOpen(S[i])) {
            isDoubleOpen = i != 0 && isOpen(S[i-1]);

            if (isDoubleOpen) {
                cnt *= 2;
            }
        } else {
            if (isClose(S[i])) {
                if (isOpen(S[i-1])) {
                    result += cnt;
                } else if (i == size-1) {
                    break;
                } else {
                    cnt /= 2;
                }

            } else {
               // 문제의 조건에 균형이 맞는 괄호라 되어 있어, 아래 코드는 빼도 무관
                return 0;
            }
        }
    }

    return result;
    }

bool isOpen(char c) {
    if (c == '(') return true;

    return false;
}

bool isClose(char c) {
    if (c == ')') return true;

    return false;
}

};

[junki-kim]

int scoreOfParentheses(string S)
{
    stack<int> m_stack;
    m_stack.push(0); // to keep the total score
    for(char c:S){
        if(c=='(')
            m_stack.push(0); //When meets '(', just push a zero to stack
        else{
            int tmp=m_stack.top(); //  balance the last '(', it stored the score of inner parentheses
            m_stack.pop();
            int val=0;
            if(tmp>0) // not zero means inner parentheses exists and double it
                val=tmp*2;
            else // zero means no inner parentheses, just using 1
                val=1;
            m_stack.top()+=val; // pass the score of this level to parent parenthese
        }   
    }
    return m_stack.top();
}

[jaeho-lee104]

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {

        int count[26]={0};
        for(char task : tasks){
            count[task-'A']++;
        }

        priority_queue<int> pq;
        for(int i=0;i<26;i++){
            if(count[i]>0)
                pq.push(count[i]);
        }

        int ans=0;
        while(!pq.empty()){
            vector<int> tmp;
            for(int i=0;i<=n;i++){
                if(!pq.empty()){
                    int m= pq.top();
                    pq.pop();
                    if(m>1){
                        tmp.push_back(--m);
                    }
                }
                ans++;
                if(pq.empty() && tmp.empty()){
                    break;
                }
            }
            for(int p : tmp){
                pq.push(p);

            }
        }

        return ans;
    }
};

[JiaYoon]

3. sliding window 실패한 솔루션(time out)

   
   class MedianFinder {
   public:
   priority_queue< int, vector<int>> maxHeap;
   priority_queue< int, vector<int>, greater<int> > minHeap;
   
   MedianFinder() {
   
   }
   
   void addNum(int num) {
       maxHeap.push(num);
       if(!minHeap.empty() && minHeap.top() < num){
           int maxmax = maxHeap.top();
           maxHeap.pop();
   
           minHeap.push(maxmax);
       }
   
       if(minHeap.size() > maxHeap.size()){
           int min = minHeap.top();
           minHeap.pop();
           maxHeap.push(min);
       }else if(minHeap.size() < maxHeap.size()){
           int max = maxHeap.top();
           maxHeap.pop();
           minHeap.push(max);
       }
   }
   
   double findMedian() {
       if(maxHeap.size() == minHeap.size()){
           return ((double)minHeap.top() + maxHeap.top())/2.0;
       }else if(maxHeap.size() > minHeap.size()){
           return maxHeap.top();
       }else {
           return minHeap.top();
       }
   }
   };

class Solution { public: vector medianSlidingWindow(vector& nums, int k) { deque dq; vector result; for(int i = 0; i < k-1; i++){ dq.push_back(nums[i]); }

    for(int i = 0; i < nums.size() - k +1;i++){
        dq.push_back(nums[k+i-1]);
        MedianFinder medianFinder;
        for(int i = 0; i < dq.size(); i++){
            medianFinder.addNum(dq.at(i));
        }
        result.push_back(medianFinder.findMedian());

        dq.pop_front();
    }

    return result;
}

};```