[Leetcode] Weekly Contest 241 후기 및 풀이

Contest : Leetcode - Weekly Contest 241

Solution code : Github

Weekly Contest 241 후기

3문제를 PASS 했습니다. 3번 문제가 평소보다도 난이도가 낮았는데도 3번을 못 풀고 4번을 통과했습니다. 끝나자마자 다시 생각하니 3번도 바로 풀렸습니다. 왜 풀이를 바로 못 떠올렸는지 이해가 안될 정도로 너무 아쉬웠습니다. 최근에 콘테스트를 못했는데 그 영향이 있었나봅니다. 다행히 4번 문제는 어려운 편이었는데도 풀어서 랭킹은 처음으로 500등대를 찍게 됐습니다.

1번 문제는 단순 Brute Force 문제였는데 콘테스트 끝난 후 풀이를 보니 XOR 특성을 이용해서 O(N)을 가능한 방법이 있어서 배울 점이 있었습니다. 2번 문제는 아이디어만 있으면 Greedy하게 풀 수 있었고 3번 문제는 (Key, value)를 저장하는 Hashmap으로 풀었습니다. 4번 문제는 DP 문제였는데 관계식을 찾는 것이 쉽지 않았습니다. 다행히 이전에 비슷한 문제를 풀어봐서 풀이를 찾을 수 있었던 것 같습니다.

문제 1. Sum of All Subset XOR Totals

문제

정수형 배열 nums가 주어집니다. nums에서 가능한 모든 부분집합의 XOR total들의 합을 구하는 문제입니다.

XOR total은 배열의 모든 정수를 XOR한 값을 의미합니다. 또한 부분집합은 동일한 값의 정수를 여러 개 포함할 수 있습니다.

제약 조건:

1 <= nums.length <= 12
1 <= nums[i] <= 20

풀이

nums의 길이가 n이라고 할 때 모든 수를 비트열로 변경하여 각각의 비트에 해당하는 값 2^(n-1), 2^(n-2), … , 2^1, 2^0을 몇개씩 더해야 하는지로 생각해봅시다.

부분집합은 모든 정수를 한번씩 포함하거나 포함하지 않거나로 정확히 반으로 나눌 수 있습니다. 이 때 XOR 연산의 특성상 모든 수의 첫번째 비트열에서 1이 하나라도 있는 경우에는 첫번째 비트열의 값 2^(n-1)을 2^(n-1)번 더한 것과 같습니다. 만약 2번째 비트열의 모든 값이 0 이라면 2^(n-2) 값은 한번도 더하지 않습니다. 모든 부분집합에서 해당 비트열은 0 이기 때문입니다.

따라서 비트열에 1이 존재하는 지 여부는 OR 연산으로 확인할 수 있고, 각각의 비트열 값에 2^(n-1)을 곱한 값을 구하면 됩니다.

더 쉬운 방법으로 모든 부분집합을 구한 후에 모든 부분집합의 XOR Total 값을 구하는 것도 가능합니다. 모든 부분집합은 0~(2^n)-1 값을 각각 비트열을 집합으로 취급하면 쉽게 구할 수 있습니다. 이 방법은 O(2^N * N) 입니다.

Time : O(N) [N: nums.length]
Space : O(1)
Tag : Bit Manipulation

C++

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int ans = 0;
        for(int i=0; i<nums.size(); i++)
            ans |= nums[i];
		return ans * pow(2, nums.size()-1);
    }
};

Python

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans = 0
        for i in nums:
            ans |= i
        return ans * 2**(len(nums) - 1)

문제 2. Minimum Number of Swaps to Make the Binary String Alternating

문제

0과 1로 이루어진 문자열 s가 주어집니다. alternating 문자열을 만들기 위한 문자의 최소 교환횟수를 구하는 문제입니다.

alternating 문자열은 인접한 두개의 문자가 서로 다른 문자인 경우를 말합니다. 만약 만들 수 없으면 -1을 출력합니다.

제약 조건:

1 <= s.length <= 1000
s[i] is either '0' or '1'.

풀이

먼저 길이가 n인 alternating 문자열은 1로 시작하는 것과 0으로 시작하는 것으로 2가지 문자열이 전부입니다.

문자열 s를 1로 시작하는 alternating 문자열로 만들기 위해서는 1인 자리인 곳에 0인 개수와 0인 자리에 1의 개수가 같아야 합니다. 그렇지 않으면 만들지 못합니다. 또한 이 개수가 최소 교환 횟수가 됩니다.

마찬가지 방법으로 0으로 시작하는 alternating 문자열을 만드는 최소 교환횟수를 구할 수 있습니다. 둘 중 작은 값이 답이 되며, 둘다 만들 수 없으면 -1 입니다.

Time : O(N) [N : s.length]
Space : O(1)
Tag : Greedy

C++

class Solution {
public:
	int minSwaps(string s) {
		int n1 = 0, n2 = 0;
		int ans = 1e9;
		for (int i = 0; i < s.size(); i += 2) if (s[i] == '0') n1++;
		for (int i = 1; i < s.size(); i += 2) if (s[i] == '1') n2++;
		if (n1 == n2) ans = min(ans, n1);

		n1 = 0, n2 = 0;
		for (int i = 0; i < s.size(); i += 2) if (s[i] == '1') n1++;
		for (int i = 1; i < s.size(); i += 2) if (s[i] == '0') n2++;
		if (n1 == n2) ans = min(ans, n1);
		return ans == 1e9 ? -1 : ans;
	}
};

Python

class Solution:
    def minSwaps(self, s: str) -> int:
        n1 = sum([1 if s[i] == '0' else 0 for i in range(0, len(s), 2)])
        n2 = sum([1 if s[i] == '1' else 0 for i in range(1, len(s), 2)])
        ans1 = n1 if (n1 == n2) else 1e9
        
        n1 = sum([1 if s[i] == '1' else 0 for i in range(0, len(s), 2)])
        n2 = sum([1 if s[i] == '0' else 0 for i in range(1, len(s), 2)])
        ans2 = n1 if (n1 == n2) else 1e9
        
        if ans1 == 1e9 and ans2 == 1e9:
            return -1
        return min(ans1, ans2)

문제 3. Finding Pairs With a Certain Sum

문제

정수형 배열 nums1 과 nums2가 주어집니다. 아래와 같은 2가지 연산을 구현하는 문제입니다.

void Add(int index, int val) : nums2[index]의 값에 val을 더한다.
int count(int tot) : nums1[i] + nums2[j] == tot인 (i, j)의 쌍의 개수를 반환한다.

제약 조건:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10^5
1 <= nums1[i] <= 10^9
1 <= nums2[i] <= 10^5
0 <= index < nums2.length
1 <= val <= 10^5
1 <= tot <= 10^9
add와 count는 각각 최대 1000번 호출

풀이

nums2의 각 정수의 값을 key로 하고 해당 key와 동일한 값을 가진 숫자의 개수를 value로 하는 해시테이블을 구성합니다.

Add 연산은 이전 값의 개수를 -1 하고, 추가되어 새로 생성된 값을 key로 하는 개수를 +1 합니다.

Count 연산은 tot - nums1[i] == nums2[j] 값을 찾아야 하므로 tot - nums1[i]의 개수가 몇개인지 구하면 됩니다.

Time [N : num1.length, M: nums2.length]
- Constructor : O(M)
- Add : O(1000*1)
- Count : O(1000*N)
Space : O(N + M)
Tag : Hashmap
해시테이블의 연산은 충돌이 거의 없다는 가정하에 O(1)로 계산했습니다.

C++

class FindSumPairs {
public:
	vector<int> n1;
	vector<int> n2;
	unordered_map<int, int> m2;
	FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
		n1 = nums1;
		n2 = nums2;
		for (int i = 0; i < n2.size(); i++)
			m2[n2[i]]++;
	}

	void add(int index, int val) {
		m2[n2[index]]--;
		n2[index] += val;
		m2[n2[index]]++;
	}

	int count(int tot) {
		int ans = 0;
		for (int i = 0; i < n1.size(); i++)
		{
			int target = tot - n1[i];
			ans += m2[target];
		}
		return ans;
	}
};

Python

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.n1 = nums1
        self.n2 = nums2
        self.m = {}
        for x in nums2:
            if x in self.m:
                self.m[x] +=1
            else:
                self.m[x] = 1

    def add(self, index: int, val: int) -> None:
        self.m[self.n2[index]] -=1
        self.n2[index] += val
        
        if self.n2[index] in self.m:
            self.m[self.n2[index]] +=1
        else:
            self.m[self.n2[index]] = 1

    def count(self, tot: int) -> int:
        return sum([self.m[tot-x] if tot-x in self.m else 0 for x in self.n1])

문제 4. Number of Ways to Rearrange Sticks With K Sticks Visible

문제

1~n 까지 서로 다른 크기를 n개의 가진 막대기가 있습니다. 막대기를 왼쪽부터 차례대로 세운 후에 왼쪽의 막대기가 높은 경우 오른쪽의 막대기는 보이지 않습니다. 이 때 왼쪽에서 정확히 k개의 막대기만 보이게 세우는 경우의 수를 구하는 문제입니다.

n과 k가 주어졌을 때, 위의 조건에 맞는 경우의 수를 구하고 만약 큰 값인 경우 modulo 값인 1e9 + 7로 나눈 나머지를 구하면 됩니다.

예를 들어, 막대기가 순서대로 [1, 3, 2, 5, 4]로 놓여져 있다면 왼쪽부터 봤을 때 [1, 3, 5]로 3가지 막대기만 보이게 됩니다. 이것은 n=5, k=3인 경우의 수 중 하나입니다.

제약 조건:

1 <= n <= 1000
1 <= k <= n

풀이

먼저 n과 k가 주어졌을때 경우의 수가 d[n][k]이라고 가정해봅시다. 그러면 경우의 수를 1 막대기가 1번째있는 경우, 2번째있는 경우, … , n번째 있는 경우의 합으로 표현할 수 있습니다.

n개의 막대기 길이를 모두 1을 더해도 경우의 수는 같습니다. 따라서 경우의 수를 쉽게 계산하기 위해 n-1개의 막대기를 세운 후에 1을 증가시키고, 1 크기를 가진 막대기를 어떤 곳에 배치해야 할지로 생각해보겠습니다.

1 막대기를 1번째에 배치한 경우의 수는 d[n-1][k-1]입니다. 그 이유는 n-1개의 막대기를 왼쪽에서 k-1개만 보이도록 세운 후에 막대기의 높이를 1씩 높인 다음 1 막대기를 가장 왼쪽에 배치한 것과 같기 때문입니다.

마찬가지로 1 막대기를 2번째에 배치한 경우의 수는 d[n-1][k]입니다. 2~n 막대기를 세운 후 2번째에 1을 배치한 것과 같기 때문입니다. 1 막대기를 3번째 ~ n번째 배치한 것도 모두 d[n-1][k]와 같습니다.

따라서 다음과 같은 Dynamic Programming으로 경우의 수를 구할 수 있습니다.

d[n][k] : n개의 막대기를 왼쪽에서 k개만 보이게 세우는 경우의 수
d[n][k] = d[n-1][k-1] + d[n-1][k] * (n-1)

Time : O(N*K) [N : n, K: k]
Space : O(N*K)
Tag : DP

C++

class Solution {
public:
#define MOD 1000000007ll
	long long d[1001][1001];
	int rearrangeSticks(int n, int k) {
		d[1][1] = 1;
		for (int i = 2; i <= n; i++)
			for (int j = 1; j <= k; j++)
				d[i][j] = (d[i - 1][j - 1] + d[i - 1][j] * (long long)(i - 1)) % MOD;
		return d[n][k];
	}
};

Python

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        mod = 1000000007
        d = [[0]*1001 for i in range(1001)]
        d[1][1] = 1
        
        for i in range(2, n+1):
            for j in range(1, k+1):
                d[i][j] = (d[i-1][j-1] + d[i-1][j]*(i-1)) % mod
        return d[n][k]