2023년 1분기

리트코드 40 - Combination Sum II (M)

class Solution {
public:
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> ret;
		vector<int> current;
		sort(candidates.begin(), candidates.end());
		search(0, target, current, candidates, ret);
		return ret;
	}
	//dfs
	void search(int startIdx, int left, vector<int>& current, const vector<int>& candidates, vector<vector<int>>& ans)
	{
		if (left < 0) return;
		if (left == 0)
		{
			ans.emplace_back(vector<int>(current));
			return;
		}
		if (startIdx >= candidates.size()) return;

		const int num = candidates[startIdx];
		
		//동일 숫자 반복 횟수 구함
		int maxRepeat = left / num;
		int numRepeat = 1;
		while (startIdx + numRepeat < candidates.size())
		{
			if (candidates[startIdx + numRepeat] == num)
				++numRepeat;
			else
				break;
		}

		int nextPos = startIdx + numRepeat;
		if (numRepeat > maxRepeat)
			numRepeat = maxRepeat;

		//안 넣어서 하나 보냄
		search(nextPos, left, current, candidates, ans);

		//n개 넣어서 보냄
		for (int i = 0; i < numRepeat; ++i)
		{
			current.emplace_back(num);
			left -= num;
			search(nextPos, left, current, candidates, ans);
		}

		for (int i = 0; i < numRepeat; ++i)
			current.pop_back();
	}
};

리트코드 1 - Two Sum (E)

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> sortedNums(nums);
		sort(sortedNums.begin(), sortedNums.end());
		for(int i=0;i< sortedNums.size();++i)
		{
			int baseNum = sortedNums[i];

			int l = i + 1;
			int r = sortedNums.size() - 1;
			int targetNum = target - baseNum;
			auto targetPos = lower_bound(sortedNums.begin() + i, sortedNums.end(), targetNum);
			if (targetPos == sortedNums.end()) continue;
			if(*targetPos == targetNum)
			{
				vector<int> ret(2);
				for(int j=0;j<nums.size();++j)
				{
					if(nums[j] == baseNum)
					{
						ret[0] = j;
						break;
					}
				}

				for (int j = 0; j < nums.size(); ++j)
				{
					if (nums[j] == targetNum && j != ret[0])
					{
						ret[1] = j;
						break;
					}
				}
				return ret;
			}
		}

		return vector<int>();
	}
};

리트코드 41 - First Missing Positive (H)

class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		for(int i=0;i<nums.size();++i)
		{
			for (int target = nums[i]; target > 0 && target <= nums.size() && target != i+1 && nums[target - 1] != nums[i]; target = nums[i])
			{
				nums[i] = nums[target - 1];
				nums[target - 1] = target;
			}
		}

		for (int i = 0; i < nums.size(); ++i)
			if (nums[i] != i + 1) return i + 1;

		return nums.size() + 1;
	}
};

 

 

리트코드 42 - Trapping Rain Water (H)

class Solution {
public:
	int trap(vector<int>& height) {
		int ans = 0;
		stack<int> s;

		for(int i=0;i<height.size();++i)
		{
			while(!s.empty() && height[s.top()] <= height[i])
			{
				const auto prev = s.top();
				s.pop();
				
				if (s.empty()) break;
				const auto left = s.top();
				const auto rain_height = min(height[left], height[i]) - height[prev];
				const auto rain_width = i - left - 1;
				ans += rain_height * rain_width;
			}

			s.push(i);
		}

		return ans;
	}
};

 

리트코드 43 - Multiply Strings (M)

class Solution {
public:
	string multiply(string num1, string num2) {
		string ans(num1.length()+ num2.length(), '0');

		int carry = 0;
		for(int j =0 ; j<num2.size() ; ++j)
		{
			int pos2 = num2.size() - j - 1;
			int digit2 = num2[pos2] - '0';
			
			for(int i=0;i<num1.size();++i)
			{
				int pos1 = num1.size() - i - 1;
				int digit1 = num1[pos1] - '0';

				int ansIdx = i + j;
				int ansPos = ans.length() - ansIdx - 1;

				int mul = digit1 * digit2;

				while(mul > 0)
				{
					int ansVal = ans[ansPos] - '0' + mul % 10;
					mul = mul / 10;
					if(ansVal > 9)
					{
						++mul;
						ansVal -= 10;
					}
					ans[ansPos] = (ansVal + '0');
					--ansPos;
				}
			}
		}

		for (int i = 0; i < ans.length(); ++i)
			if (ans[i] != '0')
				return ans.substr(i);

		return "0";
	}
};

 

 

리트코드 44 - Wildcard Matching (H)

class Solution {
public:
	bool isMatch(string s, string p) {
		s = s;
		p = p;
		vector<vector<char>> dp(s.length() + 1, vector<char>(p.length() + 1, -1));

		return isMatch(0, 0,s,p,dp);
	}
private:
	bool isMatch(int si, int pi, string& s, string& p, vector<vector<char>>& dp)
	{
		if (si >= s.length() && pi >= p.length()) return true;
		if (si >= s.length())
		{
			if (p[pi] == '*') return isMatch(si, pi + 1,s,p,dp);
			return false;
		}
		if (pi >= p.length()) return false;

		if (dp[si][pi] != -1)	return dp[si][pi] > 0 ? true : false;

		auto pattern = p[pi];
		auto input = s[si];
		bool ans = false;
		if (pattern == '*')
		{
			if (isMatch(si + 1, pi + 1,s,p,dp)) ans = true;
			else if (isMatch(si, pi + 1,s,p,dp)) ans = true;
			else if (isMatch(si + 1, pi,s,p,dp)) ans = true;
		}
		else if (pattern == '?')
		{
			if (isMatch(si + 1, pi + 1,s,p,dp)) ans = true;
		}
		else
		{
			if (pattern == input)
				if (isMatch(si + 1, pi + 1,s,p,dp)) ans = true;
		}

		dp[si][pi] = ans ? 1 : 0;
		return ans;
	}
};

 

 

리트코드 45 - Jump Game II (M)

class Solution {
public:
	int jump(vector<int>& nums) {
		if (nums.size() == 1) return 0;
		
		int numJump = 0;
		for(int i=0;i<nums.size();)
		{
			int curRange = nums[i];
			if (i + curRange >= nums.size() - 1) return ++numJump;

			int maxDist = 0;
			int targetPos = 0;
			for(int j=i+1;j<=i+curRange;++j)
			{
				const int maxRange = nums[j] + j;
				if(maxRange > maxDist)
				{
					maxDist = maxRange;
					targetPos = j;
				}
			}

			++numJump;
			i = targetPos;
		}

		return numJump;
	}
};

 

 

리트코드 46 - Permutations (M)

class Solution {
public:
	vector<vector<int>> permute(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ret;
		ret.emplace_back(vector<int>(nums));
		while (nextPermutation(nums))
			ret.emplace_back(vector<int>(nums));

		return ret;
	}

private :
	bool nextPermutation(vector<int>& nums)
	{
		int k = -1;
		for(int i=0;i<nums.size()-1;++i)
		{
			if (nums[i] < nums[i + 1])
				k = i;
		}

		if (k == -1) return false;

		int m = k+1;
		for(int i= m+1;i<nums.size();++i)
		{
			if (nums[k] < nums[i])
				m = i;
		}

		int temp = nums[k];
		nums[k] = nums[m];
		nums[m] = temp;

		reverse(nums.begin() + k + 1, nums.end());

		return true;
	}
};

 

 

리트코드 47 - Permutations II (M)

class Solution {
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ret;
		ret.emplace_back(vector<int>(nums));
		while (nextPermutation(nums))
			ret.emplace_back(vector<int>(nums));

		return ret;
	}

private :
	bool nextPermutation(vector<int>& nums)
	{
		int k = -1;
		for(int i=0;i<nums.size()-1;++i)
		{
			if (nums[i] < nums[i + 1])
				k = i;
		}

		if (k == -1) return false;

		int m = k+1;
		for(int i= m+1;i<nums.size();++i)
		{
			if (nums[k] < nums[i])
				m = i;
		}

		int temp = nums[k];
		nums[k] = nums[m];
		nums[m] = temp;

		reverse(nums.begin() + k + 1, nums.end());

		return true;
	}
};

 

 

리트코드 48 - Rotate Image (M)

class Solution {
public:
	void rotate(vector<vector<int>>& matrix) {
		int n = matrix[0].size();
		int isOdd = n % 2;
		int half = n / 2 + n % 2 - 1;

		Point pos(0, n - 1);

		for (int i = 0; i <= half; ++i)
		{
			for(int j=0;j <= half - isOdd ;++j)
			{
				int startValue = matrix[i][j];

				auto rotate1 = GetNextPos(i, j, n);
				auto rotate2 = GetNextPos(rotate1.i, rotate1.j, n);
				auto rotate3 = GetNextPos(rotate2.i, rotate2.j, n);

				matrix[i][j] = matrix[rotate3.i][rotate3.j];
				matrix[rotate3.i][rotate3.j] = matrix[rotate2.i][rotate2.j];
				matrix[rotate2.i][rotate2.j] = matrix[rotate1.i][rotate1.j];
				matrix[rotate1.i][rotate1.j] = startValue;
			}
		}
	}

private:
	struct Point
	{
		int i,j;

		Point(){}
		Point(int i, int j): j(j), i(i)	{}
	};

	//idea : 좌표를 매트릭스의 중심점에 대한 offset으로 변환하면 규칙이 보인다. 
	Point GetNextPos(int i,int j, int n)
	{
		int h = n / 2;
		Point curOffset(j-h, h-i);
		if(n%2 ==0)
		{
			if (curOffset.i >= 0) ++curOffset.i;
			if (curOffset.j <= 0) --curOffset.j;
		}
		
		auto nextOffset = GetNextOffset(curOffset);
		if(n%2 ==0)
		{
			if (nextOffset.i > 0)--nextOffset.i;
			if (nextOffset.j < 0)++nextOffset.j;
		}
		return { h - nextOffset.j, nextOffset.i + h };
	}

	Point GetNextOffset(Point offset)
	{
		//swap
		Point ret(offset.j, offset.i);

		//offset의 x부호와 다음 y부호는 같음
		if (offset.j > 0)
			ret.i = abs(ret.i);
		else
			ret.i = -abs(ret.i);

		//offset의 y부호와 다음 x부호는 다름
		if (offset.i > 0)
			ret.j = -abs(ret.j);
		else
			ret.j = abs(ret.j);

		return ret;
	}
};

 

 

리트코드 49 - Group Anagrams (M)

class Solution {
public:
	vector<vector<string>> groupAnagrams(vector<string>& strs) {
		unordered_map<long long, vector<vector<string>>> hashMap;

		for(auto& str : strs)
		{
			auto hashCode = GetHashCode(str);
			if(hashMap.find(hashCode) ==hashMap.end())
				hashMap.emplace(hashCode, vector<vector<string>>());

			auto& bucket = hashMap[hashCode];
			
			bool hasAdded = false;
			for (auto& anagram : bucket)
			{
				//같은지 비교한다. 이부분을 a,b,c 각 숫자가 몇개 있는지로 대체하면 더 빠를 것이라 기대할 수 있음.
				//근데 귀찮으니까 그냥 소팅해서 비교한다.
				string anagramStr = anagram[0];
				sort(anagramStr.begin(), anagramStr.end());
				string curStr = str;
				sort(curStr.begin(), curStr.end());
				if (anagramStr == curStr)
				{
					anagram.emplace_back(str);
					hasAdded = true;
					break;
				}
			}
			if (!hasAdded)
			{
				vector<string> newAnagram;
				newAnagram.emplace_back(str);
				bucket.emplace_back(newAnagram);
			}
		}

		vector<vector<string>> ret;
		for(auto& kvp : hashMap)
		{
			auto bucket = kvp.second;
			for(auto& anagram : bucket)
			{
				ret.emplace_back(anagram);
			}
		}
		return ret;
	}

	long long GetHashCode(string& str)
	{
		long long hash = 0;
		for(auto ch : str)
		{
			long long pos = ch - 'a';
			pos = pos << 1;
			hash += (long long)1 << pos;
		}
		hash += str.size() << 56;
		return hash;
	}
};

 

 

리트코드 51 - N-Queens (H)

struct Point
{
	int row, column;

	Point(int row, int column) : row(row) , column(column){}
};

class Solution {
	
public:
	vector<vector<string>> solveNQueens(int n) {
		dot_string_.resize(n, '.');
		vector<Point> queens;
		queens.reserve(n);
		vector<vector<string>> ans;
		Dfs(n, 0, queens, ans);
		return ans;
	}

private:
	void Dfs(int n , int row, vector<Point>& queens, vector<vector<string>>& ans)
	{
		if (row == n)
		{
			PushAnswer(queens, ans);
			return;
		}

		for(int col=0;col<n;++col)
		{
			if(!CanLocate(row, col, queens)) continue;

			queens.emplace_back(row, col);
			Dfs(n, row + 1, queens, ans);
			queens.pop_back();
		}
	}

	bool CanLocate(int row, int col, const vector<Point>& queens)
	{
		int curLeftDiagonal = row + col;
		int curRightDiagonal = row - col;

		for(auto& queen : queens)
		{
			if (queen.column == col) return false;
			if (curLeftDiagonal == queen.row + queen.column) return false;
			if (curRightDiagonal == queen.row - queen.column) return false;
		}

		return true;
	}

	void PushAnswer(const vector<Point>& queens, vector<vector<string>>& ans)
	{
		vector<string> curAns;
		curAns.reserve(queens.size());
		for(const auto& queen : queens)
		{
			dot_string_[queen.column] = 'Q';
			curAns.emplace_back(dot_string_);
			dot_string_[queen.column] = '.';
		}
		ans.emplace_back(std::move(curAns));
	}

private :
	string dot_string_;
};