2022년 2분기

프로그래머스 - 사라지는 발판 (lv3)

#include <string>
#include <vector>

using namespace std;

struct point
{
	point(int x, int y) : x(x), y(y) {}
	int x, y;
};

bool isIn(vector<vector<int>>& board, int x, int y)
{
	return x >= 0 && y >= 0 && x < board.size() && y < board[0].size() && board[x][y] == 1;
}

vector<point> getNearBy(vector<vector<int>>& board, point loc)
{
	vector<point> ret;
	int x, y;

	vector<point> diffs { {0,1}, {0,-1}, {1,0}, {-1,0} };
	for(auto diff : diffs)
	{
		int newX = loc.x + diff.x;
		int newY = loc.y + diff.y;
		if (isIn(board, newX, newY))
			ret.emplace_back(newX, newY);
	}

	return ret;
}


//이기면 true, 지면 false 리턴 / 그리고 걸린 턴수 리턴
pair<bool,int> dfs(vector<vector<int>>& board, point me, point op, int count)	//A점수 , B점수 구분해야할 필요가 ..
{
	auto nearBy = getNearBy(board, me);

	if (nearBy.size() == 0 || board[me.x][me.y] == 0)	//패배, 게임끝	... 내가 진다는건? 
	{
		return make_pair(false, count);
	}
	
	bool result = false;
	int result_count = -1;
	
	for (auto newPos : nearBy)
	{
		board[me.x][me.y] = 0;
		auto opResult = dfs(board, op, newPos, count + 1);
		board[me.x][me.y] = 1;

		bool doIWin = !opResult.first;
		int opCount = opResult.second;

		if(doIWin)	//내가 이겼다.
		{
			if(result == false)	//아직까지 다졌음
			{
				//이긴걸 고름
				result = true;
				result_count = opCount;
			}
			else //이긴적 있으면 더 빠른애 고름
			{
				if (result_count > opCount)
					result_count = opCount;
			}
		}
		else	//내가 졌다.
		{
			if (result == false)	//아직까지 지는거밖에 없음.
			{
				if (result_count < opCount) // 최대한 버틴다.
					result_count = opCount;
			}
		}
	}

	return make_pair(result, result_count);
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
	int answer = 0;

	point aPos{ aloc[0], aloc[1] };
	point bPos{ bloc[0], bloc[1] };

	auto result = dfs(board, aPos, bPos, 0);

	answer = result.second;

	return answer;
}

프로그래머스 - 신고 결과 받기

#include <string>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
	vector<int> answer;

	unordered_map<string, set<string>> reportMap;
	unordered_map<string, int> counts;
	for (auto& rpt : report)
	{
		auto space = rpt.find(' ');
		auto reporter = rpt.substr(0, space);
		auto reportee = rpt.substr(space, rpt.size() - space);

		auto & reporters = reportMap[reportee];
		reporters.emplace(reporter);
	}

	for(auto value : reportMap)
	{
		auto reporters = value.second;
		if(reporters.size() >= k)	//유저가 정지됨
		{
			for(auto & reporter : reporters)
				counts[reporter]++;
		}
	}

	for(auto id : id_list)
	{
		auto count = counts[id];
		answer.emplace_back(count);
	}
	return answer;
}

백준 13547 - 수열과 쿼리 5 (모스 알고리즘)

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

using namespace std;


const int MAX_N = 1000000;
int SqrtN;
class Solver
{
public:
	Solver()
	{

	}
	
	void ReadInput(istream& stream)
	{
		stream >> N_;
		SqrtN = sqrt(N_);
		arr_.resize(N_);
		for(int i=0;i< N_;++i)
			stream >> arr_[i];
		stream >> M_;
		queries_.resize(M_);
		for(int i=0;i<M_;++i)
		{
			stream >> queries_[i].s >> queries_[i].e;
			--queries_[i].s;
			queries_[i].idx = i;
		}
		sort(queries_.begin(), queries_.end());
	}

	vector<int> Solve()
	{
		vector<int> result(M_, 0);
		vector<int> cnt(MAX_N +2, 0);
		int numDiff = 0;
		int s = queries_[0].s;
		int e = queries_[0].e;
		
		for (int i = queries_[0].s; i < queries_[0].e; ++i)
			if (cnt[arr_[i]]++ == 0) ++numDiff;
		result[queries_[0].idx] = numDiff;

		for(int i=1; i<M_;++i)
		{
			while (queries_[i].s < s) if (cnt[arr_[--s]]++ == 0) ++numDiff;
			while (e < queries_[i].e) if (cnt[arr_[e++]]++ == 0) ++numDiff;
			while (queries_[i].s > s) if (--cnt[arr_[s++]] == 0) --numDiff;
			while (e > queries_[i].e) if (--cnt[arr_[--e]] == 0) --numDiff;

			result[queries_[i].idx] = numDiff;
		}
		return result;
	}

private:
	struct Query
	{
		int s, e, idx;
		bool operator < (const Query& other) const
		{
			return s / SqrtN != other.s / SqrtN ? s / SqrtN < other.s / SqrtN : e < other.e;
		}
	};
public :
	

private:
	vector<Query> queries_;
	vector<int> arr_;
	int M_;
	int N_;
};

int main()
{
	Solver solver;
	solver.ReadInput(cin);
	auto answer = solver.Solve();
	for (const auto & ans : answer)
		cout << ans << "\n";
	return 0;
}

백준 9202 - Boggle (문자열)

#include <string>
#include <set>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int dx[] = { 0,0,-1,-1,-1,1,1,1 };
int dy[] = { -1,1,-1,0,1,-1,0,1 };
int score[] = { 0,0,0,1,1,2,3,5,11 };
set<string> answer;
bool visited[4][4];
string boggle[4];

struct Trie {
	bool finish;
	Trie* next[26];
	Trie() : finish(false) {
		memset(next, 0, sizeof(next));
	}
	~Trie() {
		for (int i = 0; i < 26; i++)
			if (next[i] != nullptr)
				delete next[i];
	}
	void insert(string& str) {
		Trie * curNode = this;
		for(int i=0;i<str.size();++i)
		{
			int cur = str[i] - 'A';
			if (curNode->next[cur] == nullptr)
				curNode->next[cur] = new Trie();
			curNode = curNode->next[cur];
		}
		curNode->finish = true;
	}
	
	void query(int i, int j, string cur) {
		if (i < 0 || j < 0 || i >= 4 || j >= 4)return;
		if (visited[i][j])return;
		if (cur.size() >= 8)return;

		visited[i][j] = true;
		cur = cur + boggle[i][j];
		if (next[boggle[i][j] - 'A'] == '\0') {
			visited[i][j] = false;
			return;
		}
		if (next[boggle[i][j] - 'A']->finish)
			answer.insert(cur);
		for (int c = 0; c < 8; c++) {
			next[boggle[i][j] - 'A']->query(i + dx[c], j + dy[c], cur);
		}
		visited[i][j] = false;
	}
};
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int w, b;
	cin >> w;
	Trie *root = new Trie;
	for (int i = 0; i < w; i++) {
		string str;
		cin >> str;
		root->insert(str);
	}
	cin >> b;
	for (int bcnt = 0; bcnt < b; ++bcnt) {
		for (int i = 0; i < 4; ++i) cin >> boggle[i];
		answer.clear();
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				root->query(i, j, "");
			}
		}
		string longstr = *(answer.begin());
		int tscore = 0;
		for (auto ans : answer) {
			if (longstr.size() < ans.size())
				longstr = ans;
			tscore += score[ans.size()];
		}
		cout << tscore << " " << longstr << " " << answer.size() << "\n";
	}
	return 0;
}

리트코드 2 - Add Two Numbers

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode * head = new ListNode();
		ListNode * curNode = head;
		int carry = 0;
		while(true)
		{
			if (l1 == nullptr && l2 == nullptr) break;
			int num1 = 0, num2 = 0;

			if (l1 != nullptr)
			{
				num1 = l1->val;
				l1 = l1->next;
			}
			if (l2 != nullptr)
			{
				num2 = l2->val;
				l2 = l2->next;
			}

			int num3 = num1 + num2 + carry;
			if (num3 >= 10)
			{
				carry = 1;
				num3 %= 10;
			}
			else
				carry = 0;

			curNode->next = new ListNode(num3);
			curNode = curNode->next;
		}
		if(carry > 0)
			curNode->next = new ListNode(carry);

		auto answer = head->next;
		delete(head);
		return answer;
	}
};

백준 13418 - 학교 탐방하기 (최소 스패닝 트리)

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

using namespace std;

struct edge;

int N, M;
vector<edge> edges;

struct edge
{
	edge(int a, int b, int cost) : a(a), b(b), cost(cost) {}
	int a, b, cost;
};

int getRoot(vector<int> & parent, int idx)
{
	if (parent[idx] != idx)
		parent[idx] = getRoot(parent, parent[idx]);
	return parent[idx];
}

bool ascending(const edge& e1, const edge& e2)
{
	return e1.cost < e2.cost;
}

int kruskal(vector<edge> edges)
{
	int totalCost = N;
	int numSelected = 0;

	vector<int> parent(N + 1);
	for (int i = 0; i < N + 1; ++i) parent[i] = i;
	
	for(const auto & e : edges)
	{
		int rootA = getRoot(parent, e.a);
		int rootB = getRoot(parent, e.b);
		if(rootA == rootB)	
			continue;

		totalCost -= e.cost;
		parent[rootA] = rootB;

		if (++numSelected == N)
			return totalCost;
	}

	return totalCost;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> N >> M;

	edges.reserve(M+1);

	for(int i=0;i<M+1;++i)
	{
		int a, b, cost;
		cin >> a >> b >> cost;
		edges.emplace_back(a, b, cost);
	}

	sort(edges.begin(), edges.end(), ascending);	//오름차순으로 정렬 : 오르막길(0) 우선 선택
	int maxVal = kruskal(edges);

	sort(edges.rbegin(), edges.rend(), ascending);	//내림차순 정렬 : 내리막길(1) 우선 선택
	int minVal = kruskal(edges);

	cout << (maxVal * maxVal - minVal * minVal)<<endl;

	return 0;
}

리트코드 4 - Median of Two Sorted Array (Hard)

int INF = 987654321;
class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		const vector<int>* actualArray = nullptr;//둘 중 하나가 비어있을 경우 사용		
		
		if (nums1.size() == 0)
			actualArray = &nums2;
		else if (nums2.size() == 0)
			actualArray = &nums1;

		if(actualArray != nullptr)	//둘 중 하나가 비어있다.
		{
			int size = actualArray->size();
			if (size % 2 == 0)
				return (actualArray->at(size / 2) + actualArray->at(size / 2 - 1)) / 2.0;
			else
				return actualArray->at(size / 2);
		}
		
		int total = nums1.size() + nums2.size();
		int half = total / 2;
		int L = -1;
		int R = nums1.size();
		double ans = 0;

		while(L<=R)
		{
			int mid = (L + R) / 2;
			int mid2 = half - mid - 2;

			//mid2의 값이 너무 크거나 너무 작은 경우 
			if (mid2 >= (int)nums2.size())
			{
				L = mid + 1;
				continue;
			}
			if(mid2 < - 1)
			{
				R = mid - 1;
				continue;
			}
			
			int maxLeft1 = (mid >= 0) ? nums1[mid] : -INF;
			int minRight1 = (mid + 1 < nums1.size()) ? nums1[mid + 1] : INF;
			int maxLeft2 = (mid2 >= 0) ? nums2[mid2] : -INF;
			int minRight2 = (mid2 + 1 < nums2.size()) ? nums2[mid2 + 1] : INF;

			if(minRight1 < maxLeft2)
			{
				L = mid + 1;
				continue;
			}
			else if(minRight2 < maxLeft1)
			{
				R = mid - 1;
				continue;
			}

			int minRight = minRight1 < minRight2 ? minRight1 : minRight2;
			int maxLeft = maxLeft1 > maxLeft2 ? maxLeft1 : maxLeft2;
			
			if (total % 2 == 0)
				ans = (minRight + maxLeft) / 2.0;
			else
				ans = minRight;
			
			break;
		}

		return ans;
	}
};

프로그래머스 - 금과 은 운반하기 (lv3)

#include <vector>
using namespace std;

long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
	const int size = g.size();
	long long r = static_cast<long long>(1) << 52;
	long long l = 0;
	long long answer = -1;

	while (l <= r)
	{
		const long long mid = (r + l) / 2;
		long long net_gold = 0, net_silver = 0, net_weight = 0;

		for (int i = 0; i < size; ++i)
		{
			long long time = mid;
			long long cnt = 0;
			time -= t[i];
			if (time >= 0)
			{
				++cnt;
				cnt += time / (2 * t[i]);
			}

			const long long max_weight = cnt * w[i];

			net_gold += g[i] < max_weight ? g[i] : max_weight;
			net_silver += s[i] < max_weight ? s[i] : max_weight;
			net_weight += g[i] + s[i] < max_weight ? g[i] + s[i] : max_weight;
		}

		if (net_weight >= a + b
			&& net_gold >= a
			&& net_silver >= b)
		{
			//시간 충분
			answer = mid;
			r = mid - 1;
		}
		else
		{
			//시간 부족
			l = mid + 1;
		}
	}

	return answer;
}

리트코드 3 - Longest Substring Without Repeating Characters (Medium)

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int max = 0;
		int hash[128];
		memset(hash, 0, sizeof(hash));

		int cur = 0;
		int si = 0;
		for(int i=0;i<s.size();)
		{
			if(hash[s[i]] == 0) //중복아님 ..OK
			{
				if (++cur > max) max = cur;
				++hash[s[i]];
				++i;
			}
			else
			{
				--hash[s[si]];
				++si;
				--cur;
			}
		}
		return max;
	}
};

리트코드 - Longest Palindromic Substring (M)

class Solution {
public:
	string longestPalindrome(string s)
	{
		const int s_len = s.size();
		int maxL = 0, maxLen = 1;

		//홀수
		for(int i=1;i<s_len;++i)
		{
			int halfLen = 1;
			while(i - halfLen >= 0 && i + halfLen < s_len)
			{
				int cur_len = 1 + (halfLen << 1);
				int l = i - halfLen;
				int r = i + halfLen;
				if (s[l] != s[r]) break;
				if(cur_len > maxLen)
				{
					maxL = l;
					maxLen = cur_len;
				}
				++halfLen;
			}
		}

		//짝수
		for(int i=0;i<s_len;++i)
		{
			int halfLen = 1;
			while (i - halfLen + 1 >= 0 && i + halfLen < s_len)
			{
				int cur_len = halfLen << 1;
				int l = i - halfLen + 1;
				int r = i + halfLen;
				if (s[l] != s[r]) break;
				if (cur_len > maxLen)
				{
					maxL = l;
					maxLen = cur_len;
				}
				++halfLen;
			}
		}
		
		return s.substr(maxL, maxLen);
	}
};

리트코드 6 - Zigzag Conversion (M)

class Solution {
public:
	string convert(string s, int numRows) {
		if (numRows == 1) return s;
		
		const int len = static_cast<int>(s.size());
		string ans = s;	//deep copy

		const int step = numRows * 2 - 2;
		int pos = 0;

		for(int row = 0;row<numRows;++row)
		{
			int cur_idx = row;
			while (cur_idx < len)
			{
				ans[pos++] = s[cur_idx];

				if (row != 0 && row != numRows -1)	//양 끝 제외
				{
					int sub_idx = cur_idx + step - 2*row;
					if (sub_idx < len)
						ans[pos++] = s[sub_idx];
				}
				cur_idx += step;
			}
		}
		return ans;
	}
};

리트코드 7 - Reverse Integer (M)

class Solution {
public:
	int reverse(int x) {
		int ret = 0;
		int sign = 1;
		
		const int max = 2147483647;
		const int max2 = max / 10;

		if (x < 0)
		{
			if (x == -2147483648) return 0;
			sign = -1;
			x *= -1;
		}

		while (x > 0)
		{
			if (ret > max2) return 0;
			ret *= 10;

			int digit = x % 10;
			if (max - ret < digit) return 0;

			x /= 10;

			ret += digit;
		}

		ret *= sign;

		return ret;
	}
};

리트코드 9 - Palindrome Number (E)

class Solution {
public:
    bool isPalindrome(int x) {
        
        //음수이거나 끝이 0으로 끝나는 정수는 아님
        if (x < 0 || (x != 0 && x % 10 == 0))
            return false;
        
        //res는 x의 뒷부분 절반을 inverse함
        //x는 앞부분 절반만 남음
        int res = 0;
        while (x > res) {
            res = res * 10 + x % 10;
            x = x / 10;
        }
                
        return (x == res || x == res / 10);
    }
};