[Leetcode] Weekly Contest 233 후기 및 풀이
in Problem Solving on Leetcode
Contest : Leetcode - Weekly Contest 233
Solution code : Github
Weekly Contest 233 후기
3번째 콘테스트입니다. 4문제 중 3문제를 PASS 했습니다. 4번째 지난 콘테스트보다 많이 쉬운 편이었습니다. 다른 사람들도 비슷하게 느꼈는지 랭킹이 1000등대로 높진 않습니다. 괴수분들처럼 빠른 시간안에 솔루션에 도달하지는 못해도 시간 안에 모두 풀어내서 만족스러웠습니다.
문제 1. Maximum Ascending Subarray Sum
문제
정수형 배열 nums가 주어집니다. 이 nums의 부분배열(Subarray) 중 오름차순으로 이루어진 부분배열 합의 최대값을 구하는 문제입니다.
제약 조건:
1 <= nums.length <= 1001 <= nums[i] <= 100
풀이
0 <= i < nums.length 인 인덱스 i 에 대하여 nums[i] >= nums[i+1] 인 경우 nums[i+1] 로 시작하는 새로운 오름차순 부분배열이 만들어집니다. 모든 오름차순으로 이루어진 부분배열의 합 중 최대값을 구하면 됩니다.
- Time : O(N) [N :
nums.length] - Space : O(1)
- Tag :
Greedy
C++
class Solution {
public:
int maxAscendingSum(vector<int>& nums) {
int res = nums[0], sum = nums[0];
for (int s = 1; s < nums.size(); s++)
{
if (nums[s - 1] >= nums[s])
sum = nums[s];
else
sum += nums[s];
res = max(res, sum);
}
return res;
}
};
Python
class Solution(object):
def maxAscendingSum(self, nums):
res, sum = nums[0], nums[0]
for i in range(1, len(nums)):
if nums[i-1] >= nums[i]:
sum = nums[i]
else:
sum += nums[i]
res = max(res, sum)
return res
문제 2. Number of Orders in the Backlog
문제
2차원 정수형 배열 orders가 주어집니다. orders[i] = [price(i), amount(i), orderType(i)] 형태로 구성되어 있으며 orderType은 0은 구매, 1은 판매 주문이고, price의 가격에 amount 개수 만큼 주문한 것을 의미합니다.
맨처음 backlog은 비어있으며, 주어지는 orders에 대해 아래와 같이 처리합니다.
- 구매 주문인 경우, 판매 주문 리스트에서 가장 작은 가격부터 순차적으로 확인합니다. 이때
구매금액 >= 판매금액인 경우amount만큼 거래가 성사되며 나머지amount가 있으면 구매 주문 리스트에 추가됩니다. - 반대로 판매 주문인 경우, 구매 주문 리스트에서 가장 큰 가격부터 순차적으로 확인합니다. 이 때
구매금액 <= 판매금액이면amount만큼 거래가 성사되며 나머지amount가 있으면 판매 주문 리스트에 추가됩니다.
최종적으로 거래되지 않은 구매와 판매 주문에 대해 amount 총합을 구하는 문제입니다. 결과값이 큰 값인 경우 modulo 값 10^9 + 7 으로 나눈 나머지를 구합니다.
제약 조건:
1 <= orders.length <= 10^5orders[i].length == 31 <= price(i), amount(i) <= 10^9orderType(i) is either 0 or 1.
풀이
판매 주문 리스트는 Min Heap 을, 구매 주문 리스트는 Max Heap 으로 구성하면 됩니다. 구매 주문이 들어오면 판매 주문 리스트에서 가장 작은 값을 순차적으로 확인하여 거래가 가능한 만큼 처리하고 나머지는 구매 주문에 넣으면 됩니다. 판매 주문의 경우도 반대로 처리할 수 있습니다.
풀이 코드에서는 Min Heap을 구현하기 위해 price의 부호를 반전해 추가하는 방식을 사용했습니다.
- Time : O(NlogN) [N :
orders.length] - Space : O(N)
- Tag :
HeapGreedy
C++
#define MOD 1000000007ll
class Solution {
public:
struct order
{
int price;
int amount;
bool operator < (const order& rhs) const
{
return price < rhs.price;
}
};
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
priority_queue<order> buy, sell;
for(int i=0; i<orders.size(); i++)
{
int p = orders[i][0], a = orders[i][1];
if(orders[i][2])
{
while(a > 0 && !buy.empty() && buy.top().price >= p)
{
order top = buy.top(); buy.pop();
a -= top.amount;
if(a < 0)
{
top.amount = -a;
buy.push(top);
}
}
if(a > 0) sell.push({-p, a});
}
else
{
while(a > 0 && !sell.empty() && -sell.top().price <= p)
{
order top = sell.top(); sell.pop();
a -= top.amount;
if(a < 0)
{
top.amount = -a;
sell.push(top);
}
}
if(a > 0) buy.push({p, a});
}
}
int sum = 0;
while(!buy.empty()) sum = (sum + buy.top().amount) % MOD, buy.pop();
while(!sell.empty()) sum = (sum + sell.top().amount) % MOD, sell.pop();
return sum;
}
};
Python
class Solution:
def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
buy , sell = [], []
for p, a, t in orders:
if t == 1:
while a > 0 and len(buy) > 0 and -buy[0][0] >= p:
topp, topa = buy[0]
heapq.heappop(buy)
a -= topa
if a < 0:
heapq.heappush(buy, [topp, -a])
if a > 0:
heapq.heappush(sell, [p, a])
else:
while a > 0 and len(sell) > 0 and sell[0][0] <= p:
topp, topa = sell[0]
heapq.heappop(sell)
a -= topa
if a < 0:
heapq.heappush(sell, [topp, -a])
if a > 0:
heapq.heappush(buy, [-p, a])
return (sum([a for p, a in buy]) + sum([a for p, a in sell])) % (10**9 + 7)
문제 3. Maximum Value at a Given Index in a Bounded Array
문제
정수 n, index, maxSum 이 주어집니다. 다음 조건을 만족하는 정수형 배열 nums을 만들어야 합니다.
- nums.length == n
- (0 <= i < n)일 때, nums[i] 는 양수
- (0 <= i < n-1)일 때,
abs(nums[i] - nums[i+1]) <= 1 nums의 총합은maxSum를 초과하지 않음nums[index]를 최대화
이 때 최대화한 nums[index] 값을 구하는 문제입니다.
제약 조건:
1 <= orders.length <= 10^5orders[i].length == 31 <= pricei, amounti <= 10^9orderTypei is either 0 or 1.
풀이
nums[index] 값이 결정 되면 maxSum 조건에 의해 최대한 다른 element들을 작게 만들어야 하기 때문에 nums[index] 부터 nums[0] 까지는 1씩 감소하도록 만들어야 합니다. 양수 조건이 있기 때문에 1까지 감소한 경우 나머지는 감소하지 않고 모두 1이어야 합니다. nums[index] 부터 nums[n-1] 까지도 마찬가지입니다.
nums[index] == K 라고 가정하면 위와 같이 결정된 nums들의 합은 maxSum을 넘지 않아야 합니다. 넘으면 K 값을 감소시켜야하고 넘지 않으면 K 값보다 큰 값이 가능한지 확인해야 합니다.
이 K 값을 결정하기 위해 1~maxSum 사이의 값으로 Binary Search를 통해 구할 수 있습니다.
- Time : O(NlogK), (N :
n, K :maxSum) - Space : O(1)
- Tag :
Binary Search
C++
class Solution {
public:
long long getSum(long long len, long long K)
{
if (K > len)
return (K*(K + 1) / 2ll) - (K - len) * (K - len + 1) / 2ll;
else
return K * (K + 1) / 2ll + len - K;
}
int maxValue(int n, int index, int maxSum) {
int ans = 0;
int l = 1, r = 1e9;
while (l <= r)
{
int k = (l + r) / 2;
int leftLen = index + 1;
int rightLen = n - index;
long long useSum = getSum(leftLen, k) + getSum(rightLen, k) - k;
if (useSum <= (long long)maxSum)
{
ans = k;
l = k + 1;
}
else r = k - 1;
}
return ans;
}
};
Python
class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
def getSum(len, K) -> int:
if K > len:
return K * (K+1) // 2 - (K-len) * (K-len+1) // 2
else:
return K * (K+1) // 2 + len - K
ans, l, r = 0, 1, maxSum
while l <= r:
K = (l+r) // 2;
use = getSum(index+1, K) + getSum(n-index, K) - K
if use <= maxSum:
ans = K
l = K + 1
else:
r = K - 1
return ans
문제 4. Count Pairs With XOR in a Range
문제
정수형 배열 nums와 정수 2개 low, high 값이 주어집니다. 이 때 nice pairs의 개수를 구하는 문제입니다.
nice pairs는 low <= (nums[i] XOR nums[j]) <= high 을 만족하는 (i, j) 쌍의 개수를 의미합니다. (단, i < j)
제약 조건:
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 2 * 10^41 <= low <= high <= 2 * 10^4
풀이
우선 (nums[i] XOR nums[j]) <= X를 만족하는 (i, j) 쌍의 개수를 구할 수 있다고 합시다. 그러면 문제의 답은 X == high일 때의 값에서 X == low - 1일 때 값을 뺀 것과 같습니다.
그러면 임의의 i를 선택하였을 때 (nums[i] XOR nums[j]) <= X을 만족하는 j의 개수를 구해봅시다. 예를 들어 X = 20이면 비트열로 표현하면 010100 입니다. 그러면 nums[i] XOR nums[j]의 결과가 비트열 00xxxx의 개수와 0000xx의 개수(x는 0 또는 1)의 합이 됩니다. 여기서 nums[i]는 상수이므로 nums[i] XOR 00xxxx 인 prefix를 가진 nums[j]의 개수를 구할 수 있습니다. 다른 prefix도 같은 방법으로 구하면 i에 대한 j의 쌍을 구할 수 있고, 이를 모든 i에 대해 구한 개수를 더한 후에 2로 나누면 됩니다.
따라서 N개의 값들의 비트열 Prefix를 카운트하는 Trie를 구성합니다. 그런후에 모든 i에 대하여 위의 로직을 수행하면 O(16N)으로 구할 수 있습니다. 전체 Trie를 구성한 후 2로 나누어도 되지만, i번째를 순차적으로 처리하면서 Trie에 넣게되면 나누지 않아도 됩니다.
- Time : O(N)
- Space : O(1)
- Tag :
trieBit Manipulation
C++
#define MAXLEN 15
class Solution {
public:
struct trie
{
trie* node[2] = {NULL, NULL};
int cnt = 0;
void insert(trie* root, int x)
{
trie* cur = root;
for(int i=MAXLEN; i>=0; i--)
{
int next = (x >> i) & 1;
if(cur->node[next] == NULL)
cur->node[next] = new trie();
cur->node[next]->cnt++;
cur = cur->node[next];
}
}
};
int countUnderK(trie* root, int num, int k)
{
int res = 0;
trie* cur = root;
for(int i=MAXLEN; i>=0; i--)
{
if((k >> i) & 1)
{
int target = ((k >> i) & 0) ^ ((num >> i) & 1);
if(cur->node[target] != NULL)
res += cur->node[target]->cnt;
}
int next = ((k^num) >> i) & 1;
if (cur->node[next] == NULL)
break;
cur = cur->node[next];
}
return res;
}
int countPairs(vector<int>& nums, int low, int high) {
int res = 0;
trie* root = new trie();
for(int i=0; i<nums.size(); i++)
{
res += countUnderK(root, nums[i], high+1) - countUnderK(root, nums[i], low);
root->insert(root, nums[i]);
}
return res;
}
};