[Leetcode] Weekly Contest 231 후기 및 풀이

in Problem Solving on Leetcode


Contest : Leetcode - Weekly Contest 231

Solution code : Github

Weekly Contest 231 후기

Leetcode에서의 첫 콘테스트에 참여했습니다. 막상 제한시간 1시간 30분 안에 풀다보니 잘못된 솔루션도 많이 생각하고 헛코드도 많이 짠 것 같습니다. 실제 콘테스트 시간 동안에는 4문제 중 2문제만 PASS 하였습니다. 끝나고나니 3번째 문제는 비교적 금방 풀었는데 4번째 문제는 혼자 힘으로는 생각하기 어려워서 결국 Discuss에서 도움을 좀 받았습니다. 역시 갓님들의 아이디어를 보고 많이 배웁니다. 아이디어를 보고 곰곰히 생각해보니 이해가 되어서 그래도 다행입니다.

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

문제 1. Check if Binary String Has at Most One Segment of Ones

문제

‘0’과 ‘1’로 이루어진 문자열 s에 대해 연속된 ‘1’인 문자열이 하나만 존재하는지 확인하는 문제입니다.

풀이

s[0] is '1' 이라는 제약조건 때문에 연속된 ‘1’인 문자열은 반드시 하나 존재합니다.

또한 연속된 ‘1’ 문자열이 하나만 존재하려면 문자열의 [1]부터 시작하여 ‘0’ 이 나온 순간부터 그 이후의 문자는 모두 ‘0’ 이어야 합니다.

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

C++

class Solution {
public:
	bool checkOnesSegment(string s) {
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == '0')
			{
				for (int k = i + 1; k < s.size(); k++)
				{
					if (s[k] == '1')
						return false;
				}
				break;
			}
		}
		return true;
	}
};

문제 2. Minimum Elements to Add to Form a Given Sum

문제

주어진 정수형 배열인 num에 최소한의 개수로 숫자를 추가하여 num의 총합을 goal로 만드는 문제입니다. 여기서 추가하려는 숫자 X는 abs(X) <= limit 이어야 합니다.

풀이

값을 얼마나 추가할지 판단하기 위해 num의 총합을 구한 후에 goal과 차이값 diff을 구합니다.

이 diff에 대해 최소한의 개수를 추가해야 하기 때문에 abs(X) == limit인 X를 최대한 많이 추가해야 합니다. 그 개수는 abs(diff) / limit 입니다. 나머지값이 존재한다면 숫자를 하나 더 추가해야 합니다.

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

C++

class Solution {
public:
	int minElements(vector<int>& nums, int limit, int goal) {
		long long sum = 0;
		for (int i = 0; i < nums.size(); i++) 
			sum += (long long)nums[i];
		long long diff = (long long)goal - sum;
		if (diff < 0) diff = -diff;
		
		long long ans = diff / (long long)limit + ((diff % (long long)limit) ? 1 : 0);
		return ans;
	}
};

문제 3. Number of Restricted Paths From First to Last Node

문제

edges 로 이루어진 가중치가 존재하는 그래프가 주어지고, 그래프의 노드는 1 ~ n 까지의 정수로 이루어진 n개가 있습니다. 그래프에서 n과 x의 최단거리를 distanceToLastNode(x) 라고 정의하며, restricted path는 모든 a와 b에 대하여 distanceToLastNode(a) > distanceToLastNode(b)로 이루어진 경로로 정의합니다.

여기서 우리가 구하고자 하는 것은 주어진 그래프에서 노드 1와 n 간에 restricted path 의 개수입니다. 큰 값이면 Modulo 값인 1e9 으로 나눈 나머지를 출력합니다.

풀이

먼저 끝점 n은 고정되어 있으므로 모든 노드로부터 n 까지의 최단거리를 Dijkstra 알고리즘으로 계산합니다. MinHeap Dijkstra 을 이용하여 O((N+E)logN) 로 구할 수 있습니다.

모든 x에 대하여 distanceToLastNode(x)를 구했으므로 1에서 시작하는 restricted path는 최단 거리가 작아지는 방향으로만 DFS을 사용하여 이동하여 카운트하면 됩니다. 이때 d[x] = x부터 n까지의 restricted path 개수로 정의한다면 d[x] = sum(d[i]) if distanceToLastNode(x) > distanceToLastNode(i) 이므로 DP를 이용하여 O(NlogE) 으로 계산할 수 있습니다.

  • Time : O((N+E)logN + NlogE)
  • Space : O(N + E)
  • Tag : Dijkstra DFS DP

C++

#define MOD 1000000007
class Solution {
public:
	int N;
	int distance[20005];
	int cntdp[20005];
	vector<int> nodes[20005];
	vector<int> weigths[20005];

	struct node
	{
		int dist;
		int v;
		bool operator < (const node& rhs) const
		{
			return dist > rhs.dist;
		}
	};

	int DFS(int x)
	{
		int& ref = cntdp[x];
		if (ref != -1) return ref;

		ref = 0;
		for (int i = 0; i < nodes[x].size(); i++)
		{
			if (distance[x] > distance[nodes[x][i]])
				ref = (ref + DFS(nodes[x][i])) % MOD;
		}
		return ref;
	}

	int countRestrictedPaths(int n, vector<vector<int>>& edges) {
		N = n;
		for (int i = 1; i <= n; i++) distance[i] = 2e9+1, cntdp[i] =-1;
		distance[n] = 0; cntdp[n] = 1;

		for (int i = 0; i < edges.size(); i++)
		{
			nodes[edges[i][0]].push_back(edges[i][1]);
			weigths[edges[i][0]].push_back(edges[i][2]);
			nodes[edges[i][1]].push_back(edges[i][0]);
			weigths[edges[i][1]].push_back(edges[i][2]);
		}

		priority_queue<node> pq;
		pq.push({ 0, N });
		while (!pq.empty())
		{
			node top = pq.top(); pq.pop();
			if (distance[top.v] < top.dist) continue;
			for (int i = 0; i < nodes[top.v].size(); i++)
			{
				if (distance[top.v] + weigths[top.v][i] < distance[nodes[top.v][i]])
				{
					distance[nodes[top.v][i]] = distance[top.v] + weigths[top.v][i];
					pq.push({ distance[nodes[top.v][i]], nodes[top.v][i] });
				}
			}
		}

		return DFS(1);
	}
};

문제 4. Make the XOR of All Segments Equal to Zero

문제

정수형 배열 nums 와 정수 k 가 주어집니다. nums에서 어떤 인덱스에 있는 값을 원하는 값으로 변경할 수 있습니다. 이 때 nums에서 모든 연속된 k개를 XOR한 값을 0으로 만들어야 합니다. 다시 말하면 (0 <= i <= nums.size() - k)를 만족하는 모든 i 에 대하여 [i, i+k-1] 구간을 XOR한 값인 (nums[i] ^ nums[i+1] ... ^ nums[i+k-1]) = 0 이 되기 위해 변경해야 하는 최소 횟수를 구하는 문제입니다.

풀이

먼저 모든 연속된 k 개의 XOR한 값을 0으로 만들어야 하는 것으로부터

1. nums[i] ^ nums[i+1] ^ ... ^ nums[i+k-2] ^ nums[i+k-1] = 0
2. nums[i+1] ^ nums[i+2] ^ ... ^ nums[i+k-1] ^ nums[i+k] = 0

1.2 에 의해 nums[i] == nums[i+k]

위와 같은 식이 성립하므로 모든 i 에 대하여 nums[i] == nums[i+k] 임을 알 수 있습니다.

nums[i]와 모두 값이 같아야 하는 집합을 S[i] = { nums[i], nums[i+k], nums[i+2k, ...] } 라고 합시다.

그러면 S[i]의 값을 x라는 값으로 변경하는 것은 (S[i]의 개수 - S[i]에서 x의 개수) 비용이 든다고 생각할 수 있습니다.

또한 k가 정해지면 모든 nums 값을 어떻게 변경할지 생각할 필요 없이 [0, k] 구간에 있는 값을 XOR한 값이 0이 되는 것이 최소 몇번인지만 고려하면 됩니다.

인덱스 k 까지의 최소 변경값을 구하기 위해 다음과 같은 DP를 이용할 수 있습니다.

dp[i][x] : nums[i] 까지의 XOR 한 값이 x가 될 때 최소 변경값
dp[i][x] = MIN(d[i-1][x^y] + (nums[i]를 y로 변경할 때 비용)) where (0 <= y < 1024)

위 DP를 이용하면 시간복잡도가 O(K * 1024 * 1024) 이므로 아직은 TLE가 발생합니다.

더 개선할 수 있는 것은 nums[i]를 y로 변경할 때 y값 1024개를 모두 계산할 필요가 없다는 점입니다. S[i]에 없는 y는 모두 변경 비용(S[i] 개수)이 같기 때문입니다. 즉 S[i]에 있는 경우만 고려하고, S[i]에 없는 경우는 한번만 계산하면 됩니다.

- S[i]에 있는 경우: dp[i][x] = MIN(d[i-1][x^S[z]] + (nums[i]를 S[z]로 변경할 때 비용))
- S[i]에 없는 경우: dp[i][x] = (d[i-1][0...1023]) + S[i] 의 개수

위를 이용하면 O(K * 1024 * (N/K)) 이므로 O(N*1024) 입니다. (N은 nums 개수)

  • Time : O(1024 * N)
  • Space : O(N * 1024)
  • Tag : bit manipulation DP

C++

class Solution {
public:
	int minChanges(vector<int>& nums, int k) {
		int dp[2001][1024];
		int len[2001] = { 0, };
		int freq[2001][1024] = { 0, };
		
		for (int i = 0; i < nums.size(); i++)
		{
			len[i%k]++;
			freq[i%k][nums[i]]++;
		}

		for (int i = 0; i < k; i++)
			for (int x = 0; x < 1024; x++)
				dp[i][x] = 1e9;
			
		for (int x = 0; x < 1024; x++)
			dp[0][x] = len[0] - freq[0][x];
		
		for (int i = 1; i < k; i++)
		{
			int minValue = 1e9;
			for (int x = 0; x < 1024; x++) 
				minValue = min(minValue, dp[i - 1][x]);

			for (int x = 0; x < 1024; x++)
			{
				dp[i][x] = min(dp[i][x], minValue + len[i]);
				for (int z = i; z < nums.size(); z += k)
					dp[i][x] = min(dp[i][x], dp[i - 1][x^nums[z]] + len[i] - freq[i][nums[z]]);
			}
		}
		return dp[k - 1][0];
	}
};