2023년 2분기

리트코드 52 - N-Queens II (H)

struct Point
{
	int row, column;

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


class Solution {
public:
    int totalNQueens(int n) {
		vector<Point> queens;
		queens.reserve(n);
		int ans = 0;
		Dfs(n, 0, queens, ans);
		return ans;
    }

private:
	void Dfs(int n , int row, vector<Point>& queens, int& ans)
	{
		if (row == n)
		{
			++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;
	}
};

 

리트코드 53 - Maximum Subarray (M)

class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int max = nums[0];
		int curSum = 0;
		for(auto num : nums)
		{
			if (curSum < 0) curSum = num;
			else curSum += num;

			if (curSum > max)
				max = curSum;
		}

		return max;
	}
};

 

리트코드 54 - Spiral Matrix (M)

class Solution {
public:
	vector<int> spiralOrder(vector<vector<int>>& matrix) {

		int W = matrix[0].size();
		int H = matrix.size();
		vector<int> ret;
		ret.reserve(W*H);

		int visitedRow = 0;
		int visitedColumn = 1;
		int curDirIdx = 0;

		vector<int> curPos{ 0,-1 };
		while(true)
		{
			vector<int> curDir = dirs[curDirIdx];
			int togo = curDir[0] == 0 ? W - (visitedRow++) : H - (visitedColumn++);
			if (togo == 0) break;

			while(togo-- > 0)
			{
				curPos[0] += curDir[0];
				curPos[1] += curDir[1];
				ret.emplace_back(matrix[curPos[0]][curPos[1]]);
			}
			curDirIdx = curDirIdx == 3 ? 0 : curDirIdx + 1;
		}

		return ret;
	}

public:
	vector<vector<int>> dirs { {0,1}, {1,0} , {0,-1},{-1,0}};
};

 

리트코드 55 - Jump Game (M)

class Solution {
public:
	bool canJump(vector<int>& nums) {
		size_t reach = nums[0];
		if (reach >= nums.size() - 1) return true;
		
		for(size_t i = 0; i <= reach; ++i)
		{
			int curReach = i + nums[i];
			if (reach < curReach)
			{
				if (curReach >= nums.size() - 1) return true;
				reach = curReach;
			}
		}

		return false;
	}
};

 

리트코드 56 - Merge Intervals (M)

class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {

		vector<vector<int>> ret;

		sort(intervals.begin(), intervals.end(), [](const vector<int>& a,const vector<int>& b)
		{
			return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
		});

		ret.emplace_back(vector<int>{intervals[0][0], intervals[0][1]});

		for(size_t i=1;i<intervals.size();++i)
		{
			int& lastE = ret[ret.size() - 1][1];
			int s = intervals[i][0];
			int e = intervals[i][1];
			
			if(lastE < s)
				ret.emplace_back(vector<int>{s, e});
			else if(lastE < e)
				lastE = e;
		}
		
		return ret;
	}
};

 

리트코드 57 - Insert Interval (M)

class Solution {
public:
	vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {

		vector<vector<int>> ret;

		int si = lower_bound(intervals.begin(), intervals.end(), newInterval[0], [](const vector<int>& elem, int val) {
			return elem[1] < val;
		}) - intervals.begin();

		int ei = lower_bound(intervals.begin(), intervals.end(), newInterval[1], [](const vector<int>& elem, int val) {
			return elem[1] < val;
		}) - intervals.begin();
				
		for(int i=0;i<si;++i)
			ret.emplace_back(vector<int>{intervals[i][0], intervals[i][1]});

		if(intervals.size() <= si)
		{
			ret.emplace_back(newInterval);
			return ret;
		}

		int start = min(newInterval[0], intervals[si][0]);

		if(intervals.size() <= ei)
		{
			ret.emplace_back(vector<int>{start, newInterval[1]});
		}
		else if(newInterval[1] < intervals[ei][0])
		{
			ret.emplace_back(vector<int>{start, newInterval[1]});
			ret.emplace_back(vector<int>{intervals[ei][0], intervals[ei][1]});
		}
		else
		{
			ret.emplace_back(vector<int>{start, intervals[ei][1]});
		}

		for(int i=ei+1; i<intervals.size();++i)
			ret.emplace_back(vector<int>{intervals[i][0], intervals[i][1]});

		return ret;
	}
};

 

리트코드 58 - Length of Last Word (E)

class Solution {
public:
	int lengthOfLastWord(string s) {
		int cnt = 0;
		for(int i=s.length()- 1; i>=0; --i)
		{
			auto ch = s[i];
			if (ch == ' ')
			{
				if (cnt != 0) return cnt;
			}
			else
			{
				++cnt;
			}
		}

		return cnt;
	}
};

 

리트코드 60 - Permutation Sequence (H)

class Solution {
public:
	string getPermutation(int n, int k) {
		string ret;
		ret.resize(n);

		vector<int> factorial(n);
		factorial[0] = 1;
		for (int i = 1; i < n; ++i)
			factorial[i] = factorial[i - 1] * i;

		vector<int> arr(n);
		for (int i = 0; i < n; ++i)
			arr[i] = i + 1;

		k = k - 1;
		for(int i = 0 ; i < n ; ++i)
		{
			int N = n - i;
			int idx = k / factorial[N - 1];
			int num = arr[idx];
			char letter = (char)num + '0';
			ret[i] = letter;

			arr.erase(arr.begin()+idx);
			k = k % factorial[N - 1];
		}

		return ret;
	}
};

 

리트코드 62 - Unique Paths (M)

class Solution {
public:
	int uniquePaths(int m, int n) {
		vector<int> dp(n, 1);
		for(int mi=1; mi<m;++mi)
			for(int ni= 1; ni<n;++ni)
				dp[ni] = dp[ni - 1] + dp[ni];

		return dp[n - 1];
	}
};

 

리트코드 63 - Unique Paths 2 (M)

class Solution {
public:
	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

		int m = obstacleGrid.size();
		int n = obstacleGrid[0].size();

		if (obstacleGrid[0][0] == 1) return 0;
		
		obstacleGrid[0][0] = -1;
		
		for (int ni = 1; ni < n; ++ni)
		{
			if (obstacleGrid[0][ni] != 1)
				obstacleGrid[0][ni] = obstacleGrid[0][ni-1];
			else
				obstacleGrid[0][ni] = 0;
		}

		for(int mi=1;mi<m;++mi)
		{
			if (obstacleGrid[mi][0] != 1)
				obstacleGrid[mi][0] = obstacleGrid[mi - 1][0];
			else
				obstacleGrid[mi][0] = 0;
		}

		for(int mi=1;mi<m;++mi)
		{
			for(int ni=1;ni<n;++ni)
			{
				if (obstacleGrid[mi][ni] != 1)
					obstacleGrid[mi][ni] = obstacleGrid[mi - 1][ni] + obstacleGrid[mi][ni - 1];
				else
					obstacleGrid[mi][ni] = 0;
			}
		}
		
		
		return -obstacleGrid[m-1][n-1];
	}
};