2022년 3분기

리트코드 10 - Regular Expression Matching (H)

class Solution {
public:
	bool isMatch(string s, string p) {
		vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
		dp[0][0] = true;

		for (int i = 0; i <= s.size(); ++i) {
			for (int j = 1; j <= p.size(); ++j) {
				if (p[j - 1] != '*') {
					dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
				}
				else {
					dp[i][j] = (j >= 2 && dp[i][j - 2]) || (i > 0 && j > 1 && (p[j - 2] == '.' || p[j - 2] == s[i - 1]) && (dp[i - 1][j - 2] || dp[i - 1][j]));
				}
			}
		}

		return dp[s.size()][p.size()];
	}
};

리트코드 11 - Container With Most Water (M)

class Solution {
public:
	int maxArea(vector<int>& height) {
		int curLen = height.size();
		int l = 0, r = curLen - 1;
		int maxArea = 0;
		while(curLen-- > 1)
		{
			const int lh = height[l];
			const int rh = height[r];

			const int minH = lh < rh ? lh : rh;
			const int area = minH * curLen;
			if (area > maxArea) maxArea = area;

			if (rh > lh) ++l;
			else --r;
		}

		return maxArea;
	}
};

리트코드 13 - Roman to Integer (E)

class Solution {
public:
	int romanToInt(string s) {
		int num = 0;
		int subtraction = 0;
		
		for(size_t i=0;i < s.length();++i)
		{
			const int curNum = GetNum(s[i]);
			const int nextNum = (i + 1 < s.length()) ? GetNum(s[i + 1]) : -1;

			if (curNum >= nextNum)
			{
				num += curNum;
				num -= subtraction;
				subtraction = 0;
			}
			else
				subtraction += curNum;
		}
		
		return num;
	}

private :
	static int GetNum(const char ch)
	{
		switch (ch)
		{
		case 'I': return 1;
		case 'V': return 5;
		case 'X': return 10;
		case 'L' :return 50;
		case 'C': return 100;
		case 'D': return 500;
		case 'M': return 1000;
		}

		return -1;
	}
};

리트코드 14 - Longest common prefix (E)

class Solution {
public:
	string longestCommonPrefix(vector<string>& strs) {
		int i = -1;
		while(++i< strs[0].length())
		{
			char ch = strs[0][i];
			for(size_t si = 1; si<strs.size();++si)
			{
				if(i >= strs[si].length() ||
					strs[si][i] != ch)
				{
					return strs[0].substr(0, i);
				}
			}
		}

		return strs[0].substr(0, i);
	}
};

리트코드 15 - 3sum (M)

class Solution {
public:

	const long long MAX = 100000;
	
	vector<vector<int>> threeSum(vector<int>& nums) {

		vector<vector<int>> ans;
		
		int N = nums.size();
		sort(nums.begin(), nums.end());

		for(int i = 0 ; i< N;++i)
		{
			if (i > 0 && nums[i] == nums[i - 1]) continue;

			int j = i + 1, k = N - 1;
			while(j<k)
			{
				int sum = nums[i] + nums[j] + nums[k];
				if (sum > 0)
					--k;
				else if (sum < 0)
					++j;
				else
				{
					ans.push_back({nums[i], nums[j], nums[k]});
					++j;

					while (nums[j] == nums[j - 1] && j < k)
						++j;
				}

			}
		}

		return ans;
	}
};

리트코드 16 - 3sum Closest (M)

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		
		sort(nums.begin(), nums.end());
		int closest = nums[0] + nums[1] + nums[2];

		for(int i=0;i< nums.size();++i)
		{
			int j = i + 1, k = nums.size() - 1;

			while(j<k)
			{
				int sum = nums[i] + nums[j] + nums[k];

				if (sum == target) return target;

				if (abs(target - sum) < abs(target - closest))
					closest = sum;
				
				if (sum > target)
					--k;
				else
					++j;
				
			}
		}

		return closest;
	}

	static int abs(int num)
	{
		return num > 0 ? num : -num;
	}

리트코드 17 - Letter Combinations of a Phone Number (M)

class Solution {
public:
	Solution()
	{
		letters_.emplace_back(vector<char>({' '}));
		letters_.emplace_back(vector<char>{'a', 'b', 'c'});
		letters_.emplace_back(vector<char>{'d', 'e', 'f'});
		letters_.emplace_back(vector<char>{'g', 'h', 'i'});
		letters_.emplace_back(vector<char>{'j', 'k', 'l'});
		letters_.emplace_back(vector<char>{'m', 'n', 'o'});
		letters_.emplace_back(vector<char>{'p', 'q', 'r', 's'});
		letters_.emplace_back(vector<char>{'t', 'u', 'v'});
		letters_.emplace_back(vector<char>{'w', 'x', 'y', 'z'});
	}
	
	vector<string> letterCombinations(string digits) {

		vector<string> ret;
		if (digits.length() == 0) return ret;
		
		vector<vector<char>> digitLetters;
		int len = digits.length();
		
		for(char digit : digits)
		{
			int numIdx = digit - '1';
			digitLetters.push_back(letters_[numIdx]);
		}

		int totalSize = 1;
		for(int i =0; i<digitLetters.size();++i)
			totalSize *= digitLetters[i].size();
		
		for(int sub=0;sub<digitLetters[0].size();++sub)
		{
			dfs(digitLetters, ret, vector<char>(len), 0, sub);
		}
		
		return ret;
	}

	void dfs(const vector<vector<char>>& digitLetters, vector<string>& ans, vector<char> current, int idx, int subIdx)
	{
		current[idx] = digitLetters[idx][subIdx];

		if(idx+1 == digitLetters.size())
		{
			ans.emplace_back(current.begin(), current.end());
			return;
		}
		
		for(int sub = 0; sub < digitLetters[idx+1].size();++sub)
		{
			dfs(digitLetters, ans, current, idx + 1, sub);
		}
	}

private:
	vector<vector<char>> letters_;
};

리트코드 18 - 4Sum (M)

class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {

		vector<vector<int>> ans;

		sort(nums.begin(), nums.end());

		auto len = nums.size();
		for (int i = 0; i < (int)len - 3; ++i)
		{
			for (int j = i + 1; j < (int)len - 2; ++j)
			{
				int li = j + 1;
				int ri = nums.size() - 1;

				while (li < ri)
				{
					long long left_num = nums[li];
					long long right_num = nums[ri];
					long long num1 = nums[i];
					long long num2 = nums[j];
					long long sum = num1 + num2 + left_num + right_num;
					if ((long long)target == sum)
					{
						ans.push_back(vector<int>{nums[i], nums[j], nums[li], nums[ri]});

						while (li < nums.size() && nums[li] == left_num) ++li;
						while (ri >= j + 1 && nums[ri] == right_num) --ri;
					}
					else if ((long long)target > sum)
						++li;
					else
						--ri;
				}
				while (j < nums.size() - 2 && nums[j + 1] == nums[j]) ++j;
			}
			while (i < nums.size() - 3 && nums[i + 1] == nums[i]) ++i;
		}

		return ans;
	}
};

리트코드 19 - Remove Nth Node From End of List (M)

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {

		ListNode* scout = head;

		for(int i=0;i<n;++i)
			scout = scout->next;

		if (scout == nullptr) return head->next;	//첫번째껄 지움

		ListNode* predecessor = head;	//타겟의 이전 노드

		while(scout->next!=nullptr)
		{
			scout = scout->next;
			predecessor = predecessor->next;
		}

		//타겟 제거
		auto target = predecessor->next;
		predecessor->next = target->next;

		return head;
	}
};

리트코드 20 - valid-parentheses (E)

class Solution {
public:
	bool isValid(string s) {
		stack<char> stk;
		for (auto ch : s)
		{
			switch (ch)
			{
			case '(':
			case '[':
			case'{':
				stk.push(ch);
				continue;

			case ')':
			case ']':
			case '}':
				if (stk.empty()) return false;

				auto top = stk.top();

				char target;
				if (ch == ')') target = '(';
				else if (ch == ']') target = '[';
				else target = '{';

				if (top != target) return false;

				stk.pop();
				break;
			}
		}
		return stk.empty();
	}
};

리트코드 21 - Merge Two Sorted Lists (E)

struct Comparer
{
	bool operator()(ListNode** lhs, ListNode** rhs)
	{
		return (*lhs)->val > (*rhs)->val;
	}
};

 class Solution {
 public:
	 ListNode* mergeKLists(vector<ListNode*>& lists) {
		 if (lists.empty()) return nullptr;
	 	
		 priority_queue<ListNode**, vector<ListNode**>, Comparer> pq;
	 	
		 for (int i = 0; i < lists.size(); ++i)
		 {
			 if (lists[i] == nullptr) continue;
			 pq.push(&lists[i]);
		 }

		 if (pq.empty()) return nullptr;

		 auto target = pq.top(); pq.pop();
		 auto head = *target;

	 	(*target) = (*target)->next;
		if ((*target) != nullptr)
			pq.push(target);
	 	
		 head->next = merge(lists, pq);

		 return head;
	 }

 	 ListNode* merge(vector<ListNode*>& lists, priority_queue<ListNode** , vector<ListNode**>, Comparer>& pq)
	 {
		 if (pq.empty()) return nullptr;
	 	
		 ListNode ** target = pq.top();  pq.pop();

		 ListNode* head = *target;
		 (*target) = (*target)->next;

		 if ((*target) != nullptr)
			 pq.push(target);
	 	
		 head->next = merge(lists, pq);

		 return head;
	 }
 };

리트코드 22 - Generate Parentheses (M)

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		vector<string> ans;
		generateRecursively(n, 2*n - 1, 0, 0, 0, ans);

		return ans;
	}
private:
	void generateRecursively(int n, int pos, int numOpen, int numClose, int curStateAsBit, vector<string>& ans)
	{
		if(pos < 0)
		{
			string pairs;
			pairs.resize(2 * n);
			for(int i=0;i<2*n;++i)
			{
				pairs[i]= (curStateAsBit & (1 << (2*n - 1 - i))) == 0 ? ')' : '(';
			}
			ans.emplace_back(pairs);
			return;
		}
		
		if(numOpen < n)
			generateRecursively(n, pos - 1, numOpen + 1, numClose, curStateAsBit | (1 << pos), ans);

		if(numClose < numOpen)
			generateRecursively(n, pos - 1, numOpen, numClose+1, curStateAsBit, ans);
	}
};

리트코드 23 - Merge k Sorted Lists (H)

struct Comparer
{
	bool operator()(ListNode** lhs, ListNode** rhs)
	{
		return (*lhs)->val > (*rhs)->val;
	}
};

 class Solution {
 public:
	 ListNode* mergeKLists(vector<ListNode*>& lists) {
		 if (lists.empty()) return nullptr;
	 	
		 priority_queue<ListNode**, vector<ListNode**>, Comparer> pq;
	 	
		 for (int i = 0; i < lists.size(); ++i)
		 {
			 if (lists[i] == nullptr) continue;
			 pq.push(&lists[i]);
		 }

		 if (pq.empty()) return nullptr;

		 auto target = pq.top(); pq.pop();
		 auto head = *target;

	 	(*target) = (*target)->next;
		if ((*target) != nullptr)
			pq.push(target);
	 	
		 head->next = merge(lists, pq);

		 return head;
	 }

 	 ListNode* merge(vector<ListNode*>& lists, priority_queue<ListNode** , vector<ListNode**>, Comparer>& pq)
	 {
		 if (pq.empty()) return nullptr;
	 	
		 ListNode ** target = pq.top();  pq.pop();

		 ListNode* head = *target;
		 (*target) = (*target)->next;

		 if ((*target) != nullptr)
			 pq.push(target);
	 	
		 head->next = merge(lists, pq);

		 return head;
	 }
 };