[Leetcode] Weekly Contest 238 후기 및 풀이
in Problem Solving on Leetcode
Contest : Leetcode - Weekly Contest 238
Solution code : Github
Weekly Contest 238 후기
4번째 문제를 풀지 못하고 3문제를 PASS 했습니다. 1번 문제는 진법 문제이고 2, 3, 4번 모두 슬라이딩 윈도우 문제였습니다. 개인적으로는 3번 문제보다 2번 문제가 더 풀기 어려웠습니다. 2번 문제에 대한 답을 구하기 위해 O(NrootN) 방법은 바로 떠올렸으나 복잡도가 O(N^2) 같아서 구현하지 않았었는데 곰곰히 생각해보니 O(NrootN) 이어서 다행히 풀었습니다. 다만 콘테스트가 끝나고 Discuss를 보니 더 빠르게 구하는 방법이 있어서 다시 한번 더 풀었습니다. 4번 문제는 슬라이딩 윈도우 형식으로 푸는 것을 알았는데 왼쪽에서 오른쪽으로 처리하는 것만 진행하고 오른쪽에서 왼쪽으로 한번 더 해야한다는 사실을 너무 늦게 알아서 결국 틀려서 좀 아쉬웠습니다.
문제 1. Sum of Digits in Base K
문제
정수형 n과 k가 주어집니다. n을 k진법으로 바꾸었을때 각 자리수의 값을 합한 결과를 구하는 문제입니다.
제약 조건:
1 <= n <= 1002 <= k <= 10
풀이
n을 k진법으로 표기하면 n = a[x]*k^x... + a[0]*k^0 형태로 표현되으로 mod k를 통해 각 자리수 값을 / k를 통해 자리수의 위치를 알 수 있습니다.
- Time : O(logN) [N:
n] - Space : O(1)
- Tag :
GreedyBit Manipulaion
C++
class Solution {
public:
int sumBase(int n, int k) {
int sum = 0;
while (n)
{
sum += n % k;
n /= k;
}
return sum;
}
};
Python
class Solution(object):
def sumBase(self, n, k):
sum = 0
while n:
sum += n%k
n /= k
return sum
문제 2. Frequency of the Most Frequent Element
문제
frequnecy는 정수형 배열에서 임의의 element와 같은 값이 등장하는 횟수를 의미합니다.
n개의 정수형 배열 nums와 정수형 k가 주어집니다. nums의 임의의 element를 선택하여 1씩 올릴수 있는 연산을 최대 k번할 수 있습니다. 이때 가능한 frequency의 최대값을 구하는 문제입니다.
제약 조건:
1 <= nums.length <= 10^51 <= nums[i] <= 10^51 <= k <= 10^5
풀이
임의의 element로 모두 변경한다고 해봅시다. frequency를 최대화하기 위해서는 element 보다 작으면서 가장 큰 값부터 변경해야 합니다.
따라서 nums를 먼저 정렬합니다. nums[i]의 frequency는 sum[s,i] + k >= nums[i] * [s,i] 의 길이를 만족하는 가장 작은 s를 찾고 이 때 [s, i]의 길이 입니다.
위와 같은 과정은 슬라이딩 윈도우 방식으로 구할 수 있으며 모든 인덱스 i 에 대한 nums[i]의 frequency 중 가장 큰 값을 구하면 됩니다.
nums[i]의frequency는 인덱스 i보다 작은 값부터 순서대로 k에서 필요한 값만큼 빼가면서 구해도 됩니다. 단, 중복된 값이 없도록 중복된 수를 제거한 (nums[i], cnt) 형태의 Dictionary를 구성해야 합니다. 이 방법은 O(N*root(N)) 입니다.
- Time : O(N) [N :
nums.length] - Space : O(1)
- Tag :
Greedy
C++
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
long long res = 0, sum = 0, s = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
while (s < i && sum + k < nums[i] * (i - s + 1))
sum -= nums[s++];
res = max(res, i - s + 1);
}
return res;
}
};
Python
class Solution(object):
def maxFrequency(self, nums, k):
res, sum, s = 0, 0, 0
sorted(nums)
for i in range(len(nums)):
sum += nums[i]
while s < i and sum + k < nums[i] * (i - s + 1):
sum -= nums[s]
s += 1
res = max(res, i - s + 1)
return res
문제 3. Longest Substring Of All Vowels in Order
문제
어떤 문자열이 beautiful하다는 것은 다음과 같은 의미입니다.
- 모음 ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ 5개가 모두 최소한 한번씩 등장
- 문자열이 알파벳순으로 정렬됨
'a', 'e', 'i', 'o', 'u' 문자로만 이루어진 문자열 word가 주어집니다. 이 word의 부분문자열(substring) 중 가장 긴 beautiful의 길이를 구하는 문제입니다. beautiful 문자열이 없으면 0 입니다.
제약 조건:
1 <= word.length <= 5 * 10^5
풀이
beautiful 문자열을 찾기 위해서는 맨 처음 문자는 반드시 a로 시작하고 u로 끝나야 합니다. 또한 a가 등장하면 현재 문자인 a 또는 다음 문자인 e만이 나올 수 있습니다.
첫번째 문자부터 확인하면서 조건에 맞는 문자열을 찾을 때까지 반복하면 됩니다.
- Time : O(N), [N :
word.length] - Space : O(N)
- Tag :
Greedy
C++
class Solution {
public:
int longestBeautifulSubstring(string word) {
int res = 0, v = 0, o = 0;
char order[] = { 'a', 'e', 'i', 'o', 'u', 'u' };
for (int i = 0; i < word.size(); i++)
{
if (v == 0 && word[i] != 'a') continue;
if (word[i] == order[o]) v++;
else if (word[i] == order[o + 1]) v++, o++;
else if (word[i] == 'a') v = 1, o = 0;
else v = 0, o = 0;
if (order[o] == 'u') res = max(res, v);
}
return res;
}
};
Python
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
ch = "aeiouu"
res, v, o = 0, 0, 0
for c in list(word):
if v == 0 and c != 'a':
continue
if c == ch[o]:
v += 1
elif c == ch[o+1]:
v += 1
o += 1
elif c == 'a':
v = 1
o = 0
else:
v = 0
o = 0
if ch[o] == 'u':
res = max(res, v)
return res
문제 4. Maximum Building Height
문제
n개의 건물을 만들어야 합니다. 각 건물의 번호는 1~n입니다. 건물을 지을때는 몇가지 조건이 있습니다.
- 건물의 높이는 1 이상
1번 건물의 높이는 0- 모든 인접한 건물의 높이의 차이는
1이 넘지 않음 (0또는1)
또한 2차원 정수형 배열인 restrictions 값이 주어집니다. restrictions[i] = [id(i), maxHeight(i)] 형태이며 건물번호 id(i)는 maxHeight(i) 보다 작거나 같은 높이로만 지을 수 있음을 의미합니다.
위 조건을 만족하면서 건물을 지을 때 모든 건물 중 가장 높은 건물을 최대화하도록 지으면 가장 높은 건물의 높이를 구하는 문제입니다.
단 restrictions에서 중복된 빌딩 번호가 나오지 않으며, 빌딩번호 1은 나오지 않음이 보장됩니다.
제약 조건:
2 <= n <= 10^90 <= restrictions.length <= min(n - 1, 10^5)2 <= id(i) <= nidi is unique.0 <= maxHeight(i) <= 10^9
풀이
건물의 높이를 최대화하기 위해서는 임의의 두점 (i, j) 를 선택했을 때 건물의 형태가 왼쪽(i)에서 오른쪽(j)으로 +1 씩 올라가는 형태, -1 씩 내려가는 형태, 왼쪽에서 +1 씩 올라가다가 x를 찍은 후 -1 하면서 오른쪽으로 내려오는 형태로 총 3가지가 나타납니다.
이때 restirctions에서 건물번호로 정렬한 후 왼쪽에서 오른쪽으로 +1 씩 올라간다고 가정했을때 각각의 maxHeight를 업데이트할 수 있습니다. 또한 오른쪽에서 왼쪽으로 +1 씩 올라간다고 가정했을때 각각의 maxHeight를 다시 업데이트할 수 있습니다.
위와 같은 수행을 하면 restrictions 에 나온 건물번호들의 높이는 maxHeight로 고정됩니다. 따라서 restrictions 에 나온 건물번호만 가지고 건물의 최대 높이를 구할 수 있습니다.
+1 씩 올라가는 형태는 우측의 건물이 제일 높고, -1씩 내려가는 형태는 왼쪽의 건물이 제일 높습니다. 올라갔다가 내려가는 건물 형태에서 건물의 최대 높이는 (건물번호의 차이 + 왼쪽 건물의 높이 + 오른쪽 건물의 높이) / 2 임을 알 수 있습니다.
- Time : O(NlogN) [N :
restrictions.length] - Space : O(1)
- Tag :
Greedy
C++
class Solution {
public:
int maxBuilding(int n, vector<vector<int>>& restrictions) {
restrictions.push_back({ 1, 0 });
sort(restrictions.begin(), restrictions.end());
if (restrictions[restrictions.size() - 1][0] != n)
restrictions.push_back({ n, 1000000000 });
for (int i = 0; i < restrictions.size() - 1; i++)
{
int c = restrictions[i + 1][0] - restrictions[i][0];
restrictions[i+1][1] = min(restrictions[i+1][1], restrictions[i][1] + c);
}
for(int i = restrictions.size() - 1; i > 0; i--)
{
int c = restrictions[i][0] - restrictions[i - 1][0];
restrictions[i-1][1] = min(restrictions[i-1][1], restrictions[i][1] + c);
}
int res = 0;
for(int i = 0; i < restrictions.size() - 1; i++)
{
int len = restrictions[i+1][0] - restrictions[i][0];
int h1 = restrictions[i][1];
int h2 = restrictions[i+1][1];
res = max(res, max(h1, h2));
res = max(res, (len + h1 + h2) / 2);
}
return res;
}
};
Python
class Solution:
def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
restrictions.append([1, 0])
restrictions.sort()
if restrictions[-1][0] != n:
restrictions.append([n, 10**9])
for i in range(len(restrictions)-1):
c = restrictions[i+1][0] - restrictions[i][0]
restrictions[i+1][1] = min(restrictions[i+1][1], restrictions[i][1] + c)
for i in range(len(restrictions)-1, 0, -1):
c = restrictions[i][0] - restrictions[i-1][0]
restrictions[i-1][1] = min(restrictions[i-1][1], restrictions[i][1] + c)
res = 0
for i in range(len(restrictions)-1):
l = restrictions[i+1][0] - restrictions[i][0]
h1, h2 = restrictions[i][1], restrictions[i+1][1]
res = max(res, h1, h2, (l + h1 + h2) // 2)
return res