[Leetcode] Biweekly Contest 50 후기 및 풀이

in Problem Solving on Leetcode


Contest : Leetcode - Biweekly Contest 50

Solution code : Github

Biweekly Contest 50 후기

4번 문제를 풀지 못하고 3문제를 PASS 했습니다. 4번 문제는 패턴을 얼핏 찾기는 했는데 짧은 시간 동안에는 올바른 솔루션을 찾지 못했습니다. 1번은 간단한 그리디 , 2번은 원의 방정식, 3번은 비트 연산에 대한 문제였습니다. 4번은 수학에 가까운 문제였는데 컨테스트가 끝나고 Discuss의 좋은 설명들을 봐도 제대로 이해하기가 어려웠습니다. 브루트포스하게 코딩해보면 패턴이 얼추 보였던 문제라 이정도로 만족하고 PASS만 받고 넘어갔습니다.

문제 1. Minimum Operations to Make the Array Increasing

문제

정수형 배열 nums 가 주어집니다. 임의의 element를 선택하여 값을 1 올리는 연산을 할 수 있습니다. 이 연산을 사용하여 nums를 strictly increasing하게 만드는 최소 연산 횟수를 구하는 문제입니다.

여기서 strictly increasing는 nums[i] < nums[i+1] for all 0 <= i < nums.length - 1 이므로 오름차순(1이상 커지는) 배열을 말합니다.

제약 조건:

  • 1 <= nums.length <= 5000
  • 1 <= nums[i] <= 10^4

풀이

최소 연산횟수를 구하기 위해서는 nums[i-1] >= nums[i] 인 경우에는 nums[i]를 nums[i-1]+1로 만들어야 합니다. 이미 nums[i-1] < nums[i]인 경우에는 nums[i]을 변경할 필요가 없습니다. 이 것을 nums[1]부터 시작하여 값을 변경하면서 연산횟수를 카운트하면 됩니다.

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

C++

class Solution {
public:
	int minOperations(vector<int>& nums) {
		int res = 0;
		for (int i = 1; i < nums.size(); i++)
		{
			if (nums[i - 1] >= nums[i])
			{
				res += (nums[i - 1] + 1 - nums[i]);
				nums[i] = nums[i - 1] + 1;
			}
		}
        return res;
	}
};

Python

class Solution(object):
    def minOperations(self, nums):
        res = 0
        for i in range(1, len(nums)):
            if nums[i-1] >= nums[i]:
                res += nums[i-1] + 1 - nums[i]
                nums[i] = nums[i-1] + 1
        return res

문제 2. Queries on Number of Points Inside a Circle

문제

2D 평면 (x,y)에서 N개의 points가 주어지며 points[i] = [x(i), y(i)] 로 구성되어 있습니다. 그리고 M개의 queries가 주어지는데 queries[j] = [x(j), y(j), r(j)] 형태입니다. 이 때 각각의 queries에 대한 답을 구해야 하며, queries[j] = x, y, r은 (x,y) 좌표에 반지름이 r인 원을 의미하며, points 중 몇개가 이 원 안에 존재하는지를 구하는 문제입니다.

단, 원의 경계에 있는 포인트도 원 안에 있는 것으로 간주합니다.

제약 조건:

  • 1 <= points.length <= 500
  • 0 <= x​​​​(​​i), y(​​​​​​i) <= 500
  • 1 <= queries.length <= 500
  • 0 <= x(j), y(j) <= 500
  • 1 <= r(j) <= 500
  • 모든 좌표는 정수

풀이

원의 중심의 좌표가 (x, y) 이고, 반지름이 r 인 경우 원의 방정식은 (X-x)^2 + (Y-y)^2 = r^2 입니다. 따라서 원이 (x, y, r) 이고, 어떤 점(px, py) 가 원의 경계를 포함한 내부에 있기 위해서는 (px - x)^2 + (py - y)^2 <= r^2 이어야 합니다.

  • Time : O(N*M) [N : points.length, M: queries.length]
  • Space : O(1)
  • Tag : Math

C++

class Solution {
public:
	bool inCircle(int x, int y, int r, int px, int py)
	{
		return ((px - x)*(px - x) + (py - y)*(py - y)) <= r * r;
	}
	vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
		vector<int> res;
		for (int k = 0; k < queries.size(); k++)
		{
			int cnt = 0;
			for (int i = 0; i < points.size(); i++)
				if (inCircle(queries[k][0], queries[k][1], queries[k][2], points[i][0], points[i][1]))
					cnt++;
			res.push_back(cnt);
		}

		return res;
	}
};

Python

class Solution(object):
    def countPoints(self, points, queries):
        return [sum([1 if ((px - x)**2 + (py - y)**2 <= r**2) else 0 for px, py in points]) for (x, y, r) in queries]

문제 3. Maximum XOR for Each Query

문제

정수형 배열인 N개의 nums와 정수값 maximumBit가 주어집니다. 그리고 우리는 N번의 query에 대한 답을 구해야 합니다.

  1. k < 2^maximumBit 조건을 만족하는 k 에 대하여 nums[0] ^ num[1] ^ ... nums[nums.length-1] ^ k 값을 최대화 하는 k를 찾는 것입니다. 이 값이 i번째 query에 대한 답입니다.
  2. nums의 마지막 element를 삭제합니다.

위를 N번 반복하여 각각에 대한 답을 순서대로 구해야 합니다.

제약 조건:

  • 1 <= nums.length <= 10^5
  • 1 <= maximumBit <= 20
  • 0 <= nums[i] < 2^maximumBit
  • nums​​​ 는 오름차순으로 정렬됨

풀이

k < 2^maximumBit 를 만족한다는 것은 k를 비트열로 봤을때 일의 자리로부터 maximumBit 미만의 자리수에는 1 또는 0을 선택할 수 있고, maximumBit번째 이상인 비트부터는 모두 0 이어야 합니다.

(xor sum) ^ k 값이 최대이기 위해서는 xor sum 값의 maximumBit 미만의 자리수를 모두 1로 만들 수 있도록, 해당 자리수들만 비트 반전한 값이 k 값과 같아야 합니다.

또한 마지막 element를 삭제하는 것은 xor sum에다가 마지막 element를 다시 XOR 한 것과 같습니다.

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

C++

class Solution {
public:
	vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
		int xorsum = 0;
		for (int i = 0; i < nums.size(); i++) 
			xorsum ^= nums[i];
		
		int bits = (1 << maximumBit)-1;

		vector<int> res;
		for (int i = nums.size() - 1; i >= 0; i--)
		{
			res.push_back((~(xorsum & bits)) & bits);
			xorsum ^= nums[i];
		}
        return res;
	}
};

Python

class Solution(object):
    def getMaximumXor(self, nums, maximumBit):
        xsum = 0
        xorsumList = []
        for x in nums:
            xsum ^= x
            xorsumList.append(xsum)
            
        bits = (1<<maximumBit)-1
        return [((~(xorsum & bits)) & bits) for xorsum in reversed(xorsumList)]

문제 4. Minimum Number of Operations to Make String Sorted

문제

문자열 s가 주어집니다. s를 다음과 같은 작업을 정렬될 때까지 반복합니다.

  1. 1 <= i < s.length 와 s[i] < s[i-1]을 만족하는 가장 큰값 i 을 찾습니다.
  2. i <= j < s.length 와 [i,j] 구간에 존재하는 모든 k 값에 대해 s[k] < s[i-1]를 만족하는 가장 큰값 j를 찾습니다.
  3. i-1 과 j 인덱스의 값을 서로 스왑합니다.
  4. 문자열 s의 인덱스 i부터 s.length-1 까지 값을 reverse 합니다.

총 몇번의 작업을 하게 될지 구하는 문제입니다. 만약 값이 크면 modulo 값 10^9+7 로 나눈 나머지를 구합니다.

제약 조건:

  • 1 <= s.length <= 3000
  • s 의 문자는 모두 소문자​

풀이

먼저 해야하는 작업을 Bruteforce 하게 만들어 출력해보면 순열의 경우의 수로 계산되는 패턴을 발견할 수 있습니다. 사실 수학적으로 왜 그렇게 나오는지는 결국 이해를 못해서 이 부분은 설명이 어렵습니다ㅠㅠ. 어떤 패턴인지만 설명하겠습니다.

편의상 숫자로된 문자열로 위의 작업방식으로 정렬해보면 필요한 횟수는

  1. “54321”을 정렬하려면 5! 입니다.
  2. “613579” 문자열은 3*5! 이고, 일반화하면 (j-i) * ([i, s.length-1] 구간의 개수)! 입니다.
  3. “613355579” 문자열은 (6 * 7!) / 2! / 3! 이고, 마찬가지로 일반화하면 (j-i) * ([i, s-length-1] 개수)! / (문자별 같은 문자열 개수)! 입니다.

임을 알 수 있습니다.

즉 s[i-1]이 이동해야 하는 위치까지의 거리와 이미 정렬된 [i, s.length-1]의 순열의 개수의 곱 만큼 횟수가 진행되면 [i-1, s.length-1] 구간이 정렬됩니다.

문자는 총 26개 이므로 각각을 c[26] 형식으로 카운팅해두면, s[i-1]가 이동해야 하는 위치는 c[0] + ... + c[s[i-1]-'a'-1]이 됩니다.

팩토리얼의 값이 커질 수 있기 때문에 나누는 방법은 페르마의 소정리를 이용할 수 있습니다.

페르마의 소정리에 따라 (a^p % p) = a 이므로 a를 나눈다는 것은 a^(p-2) % p를 곱해주는 것으로 처리가 가능합니다.

  • Time : O(26N) [N : s.length]
  • Space : O(1)
  • Tag : Math String

C++

class Solution {
public:
#define MOD 1000000007ll
	long long pow(int x, int n)
	{
		if (n == 0) return 1;
		
		long long value = pow(x, n / 2);
		value = (value * value) % MOD;
		if (n & 1) value = (value * (long long)x) % MOD;
		return value;
	}

	int makeStringSorted(string s) {
		long long res = 0;
		long long f[3001]; f[0] = 0, f[1] = 1;
		for (long long i = 2; i <= 3000; i++) f[i] = (f[i - 1] * i) % MOD;

		int c[26] = { 0, };
		for (int i = s.size() - 1; i >= 0; i--)
		{
			long long sum = 0, value = 0;
			int ch = s[i] - 'a';
			c[ch]++;
			for (int k = 0; k < ch; k++) sum += c[k];
			value = (sum * f[s.size() - i - 1]) % MOD;
			for (int k = 0; k < 26; k++) if(c[k] > 1) value = (value * pow(f[c[k]], MOD - 2)) % MOD;

			res = (res + value) % MOD;
		}
		return res % MOD;
	}
};

Python

class Solution:
    def makeStringSorted(self, s: str) -> int:
        mod = 10**9 + 7
        c = [0] * 26
        f = [0, 1]
        for i in range(2, 3001):
            f.append((f[i-1] * i) % mod)
        
        res = 0
        for i in range(len(s)-1, -1, -1):
            ch = ord(s[i]) - ord('a')
            c[ch] += 1
            value = sum(c[:ch]) * f[len(s) - i - 1]
            for k in range(26):
                if c[k] > 1:
                    value = (value * (pow(f[c[k]], mod-2, mod))) % mod
            res = (res + value) % mod
        return res