1. 정렬

[jaeho-lee104]

풀이

• https://leetcode.com/problems/sort-colors/
• https://leetcode.com/problems/intersection-of-two-arrays/

숙제

• https://leetcode.com/problems/find-common-characters/ ( 중환, 재호)
• https://leetcode.com/problems/sort-list/ ( 승호, 영륜 )
• https://leetcode.com/problems/wiggle-sort-ii/ (준기, 지아 )

[scsc3313]

148. sort-list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
      ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;

        ListNode *slow=head,*fast=head;
        while(slow->next!=NULL && fast->next!=NULL && fast->next->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode *last=slow->next;
        slow->next=NULL;
        ListNode *pre=sortList(head);
        ListNode *las=sortList(last);
        return merge(pre,las);
    }

    ListNode* merge(ListNode *l1 , ListNode *l2)
    {
        ListNode* dummy=new ListNode(0);
        ListNode* p=dummy;
        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                p->next=l2;
                p=p->next;
                l2=l2->next;
            }
            else
            {
                p->next=l1;
                p=p->next;
                l1=l1->next;
            }
        }
        if(NULL==l1) p->next=l2;
        if(NULL==l2) p->next=l1;
        return dummy->next;

    }
};

[junki-kim]

#include <vector>
#include <algorithm>
#include <iostream>

class Solution
{
public:
    void wiggleSort1(std::vector<int> &nums)
    {
        std::sort(nums.begin(), nums.end());
        std::vector<int> sorted;

        int center = nums.size() / 2;

        if (nums.size() % 2 != 0)
        {
            center++;
        }

        int left = center - 1;
        int right = nums.size() - 1;

        for (; left >= 0; left--, right--)
        {
            sorted.push_back(nums.at(left));

            if (right >= center)
            {
                sorted.push_back(nums.at(right));
            }
        }

        nums = sorted;
    }
};

void print(std::vector<int> const &input)
{
    for (int i = 0; i < input.size(); i++)
    {
        std::cout << input.at(i) << ' ';
    }
}

int main()
{
    // static const int arr[] = {1, 5, 1, 1, 6, 4};
    static const int arr[] = {1, 1, 2, 1, 2, 2, 1};
    // static const int arr[] = {4, 5, 5, 6};
    std::vector<int> inputs(arr, arr + sizeof(arr) / sizeof(arr[0]));

    Solution solution;
    solution.wiggleSort1(inputs);

    print(inputs);
}

https://leetcode.com/problems/wiggle-sort-ii/discuss/77684/Summary-of-the-various-solutions-to-Wiggle-Sort-for-your-reference

[Leeyoungryun]

148. sort list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
       vector<int> v;

        ListNode* temp = head;
        while (true) {
            if (temp == NULL) {
                break;
            }

            v.push_back(temp->val);
            if (temp->next != NULL) {
                temp = temp->next;
            } else {
                break;
            }
        }

        std::sort(v.begin(), v.end());

        ListNode* _temp = head;
        for (int i = 0; i < v.size();i++){
            _temp->val = v[i];
            if (_temp->next != NULL) {
                 _temp = _temp->next;  
            }             
        }

        return head;
    }
};

[JiaYoon]

324. Wiggle Sort II

https://leetcode.com/problems/wiggle-sort-ii/submissions/

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> answer;

        sort(nums.begin(),nums.end(), greater<int>());

        int size = (int)nums.size()/2;
        for(int i = 0; i < size; i++){
            answer.push_back(nums[i+size]);
            answer.push_back(nums[i]);
        }

        if(nums.size() % 2 == 1){
            answer.push_back(nums[nums.size()-1]);
        }

        nums=answer;
    }
}; 

[jaeho-lee104]

1002. Find Common Characters

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        int check[100][27] ={0,};
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A[i].length();j++){
                check[i][A[i][j]-'a']++;
            }
        }

        int ans[27]={0,};
        for(int i=0;i<27;i++){
            int count =1000;
            for(int j=0;j<A.size();j++){
                count =min(count, check[j][i]);
            }
            ans[i]=count;
        }
        vector<string> ret;
        for(int i=0;i<27;i++){
            if(ans[i]>0 && ans[i]!=1000){
                for(int j=0;j<ans[i];j++){
                    char ch = i+'a';
                    string str;
                    str.push_back(ch);
                    ret.push_back(str);
                }
            }
        }
        return ret;
    }
};

[junki-kim]

https://leetcode.com/problems/kth-largest-element-in-an-array/ 각자 풀어보기