[Leetcode] Weekly Contest 232 후기 및 풀이

Contest : Leetcode - Weekly Contest 232

Solution code : Github

Weekly Contest 232 후기

운이 좋게도 4문제 모두 PASS 했습니다. 지난 콘테스트보다 비교적 쉽게 느껴졌습니다. 다른 사람들도 비슷하게 느꼈는지 랭킹이 1000등대로 높진 않습니다. 괴수분들처럼 빠른 시간안에 솔루션에 도달하지는 못해도 시간 안에 모두 풀어내서 만족스러웠습니다.

이제 솔루션을 적어봅니다.

문제 1. Check if One String Swap Can Make Strings Equal

문제

길이가 같은 2개의 문자열 s1, s2이 주어지면, s1에서 문자를 딱 한번만 Swap하여 s2와 같아질 수 있는지를 판단하는 문제입니다.

풀이

이 문제에서는 문자열의 길이가 N <= 100 이라는 제약때문에 임의의 인덱스 (i, j)를 선택하여 Swap해본 후 문자열이 같은지를 체크해보는 O(N^3) 도 가능합니다.

더 빠른 방법은 정확히 한번만 같아지기 위해서는 s1과 s2가 같은 문자열이거나 문자열 s1과 s2 에서 같은 인덱스의 문자가 정확히 2개만 다르고 각각에 사용된 그 2개의 문자가 같다는 것을 이용하면 됩니다.

Time : O(N)
Space : O(1)
Tag : Greedy

C++

class Solution {
public:
	bool areAlmostEqual(string s1, string s2) {
		int cnt = 0;
		int a = -1, b = -1;
		for (int i = 0; i < s1.size(); i++)
		{
			if (s1[i] != s2[i])
			{
				cnt++;
				if (a == -1) a = i;
				else b = i;
			}
		}
		
		if (cnt == 0 || (cnt == 2 && s1[a] == s2[b] && s1[b] == s2[a])) return true;
		else return false;
	}
};

문제 2. Find Center of Star Graph

문제

1 ~ n 번호로 n 개의 노드를 가진 그래프가 주어집니다. 이 그래프는 정확히 한개의 노드가 중앙에 있고 다른 모든 노드들이 중앙에 연결되어 있습니다. edges 가 주어질 때 중앙 노드가 무엇인지 찾는 문제입니다.

풀이

모든 노드가 중앙 노드와 연결되어 있으므로 2개의 edge만 확인해보면 됩니다. 각각의 edge에서 같은 노드번호를 가진 것이 중앙노드임을 알 수 있습니다.

Time : O(1)
Space : O(1)
Tag : Greedy

C++

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        if(edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1])
            return edges[0][0];
        else
            return edges[0][1];
    }
};

문제 3. Maximum Average Pass Ratio

문제

학교에서 N개의 classes 가 있고 각 class별로 합격자수와 전체 학생수 classes[i] = [pass[i], total[i]] 가 주어집니다.

extraStudents의 값은 어떤 Class든 참여시켜서 합격이 될 수 있는 학생들의 수 입니다. 이 extraStudents를 원하는 Class에 참석시켜 전체 평균 합격률을 최대화한 값이 무엇인지를 계산하는 문제입니다.

여기서 합격률은 각 Class의 합격자수를 전체 학생수로 나눈 값이고 전체 평균 합격률은 각 Class의 합격률의 합을 전체 Class 수로 나눈 값을 의미합니다.

풀이

extraStudents를 어떤 Class[i]에 배치할 경우 합격률은 ((pass[i] + 1) / total[i] + 1) 이 됩니다. 전체 평균 합격률이 높이려면 Class 중 합격률 p% 값을 가장 높일 수 있는 곳에 배치해야 합니다. 즉 ((pass[i] + 1) / total[i] + 1) - ((pass[i] / total[i]) 값이 가장 높은 i에 배치해야 합니다. 이 값을 gain값으로 정의하고 계산합니다.

우리는 빠른 시간안에 가장 높은 gain을 가진 class[i]를 찾을 수 있도록 힙을 구성합니다. 그런 후에 extraStudents가 있는 만큼 해당 Class에 배치하는 것을 반복하면 됩니다.

Time : O(MlogN), (N : Class 수, M : extraStudnets 수)
Space : O(N)
Tag : Heap

C++

class Solution {
public:
	struct item
	{
		int passes;
		int students;

		double gain;
		bool operator < (const item& rhs) const
		{
			return gain < rhs.gain;
		}
	};

	double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
		priority_queue<item> pq;
		for (int i = 0; i < classes.size(); i++)
		{
			int x = classes[i][0];
			int y = classes[i][1];
			pq.push({ x, y, (double)(x + 1) / (double)(y + 1) - (double)x / (double)y });
		}

		while (extraStudents--)
		{
			item top = pq.top(); pq.pop();
			int x = top.passes + 1;
			int y = top.students + 1;
			pq.push({ x, y, (double)(x + 1) / (double)(y + 1) - (double)x / (double)y });
		}

		double ans = 0.0;
		while (!pq.empty())
		{
			item top = pq.top(); pq.pop();
			ans += (double)top.passes / (double)top.students;
		}
		ans /= (double)classes.size();
		return ans;
	}
};

문제 4. Maximum Score of a Good Subarray

문제

정수형 배열 nums 와 정수 k 가 주어집니다. 어떤 부분배열 (i,j) 의 점수는 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) where (i<=k<=j) 으로 정의 합니다. 이 점수를 최대화할 수 있는 (i, j)를 찾아 계산하는 문제입니다.

풀이

먼저 k를 포함한 부분배열 (i,j)를 선택해야 합니다. 그래서 k부터 시작하여 i 값은 작아지도록, j 값은 커지도록 포인터를 이동시키면서 모든 경우를 탐색하면 됩니다. 우리는 (i, j) 사이의 min 값을 모두 탐색하기 위해서는 nums[i]와 nums[j] 중 큰 값으로 포인터를 이동해야 모든 경우를 탐색할 수 있습니다.

Time : O(N)
Space : O(1)
Tag : Greedy

C++

class Solution {
public:
	int maximumScore(vector<int>& nums, int k) {
		int score = nums[k];
		int mn = nums[k];
		int lo = k;
		int hi = k;

		while (0 < lo || hi < nums.size() - 1)
		{
			if (lo == 0)
				hi++;
			else if (hi == nums.size() - 1)
				lo--;
			else if (nums[lo - 1] < nums[hi + 1])
				hi++;
			else
				lo--;

			mn = min(mn, min(nums[lo], nums[hi]));
			score = max(score, mn * (hi - lo + 1));
		}

		return score;
	}
};