class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
ans = []
# O(n^2 sol..)
for i in range(len(queries)):
# low & high are index
high = max(queries[i])
low = min(queries[i])
if high == low or heights[high] > heights[low] :
ans.append(high)
continue
else:
cond = False
for j in range(high+1,len(heights)):
if heights[j] > heights[low] and heights[j] > heights[high]:
cond = True
ans.append(j)
break
if not cond :
ans.append(-1)
return ansYou are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.
If a person is in building i, they can move to any other building j if and only if i < j and heights[i] < heights[j].
You are also given another array queries where queries[i] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.
Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the ith query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.
Example 1:
Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
Output: [2,5,-1,5,2]
Explanation: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2].
In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5].
In the third query, Alice cannot meet Bob since Alice cannot move to any other building.
In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].
In the fifth query, Alice and Bob are already in the same building.
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.
Example 2:
Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
Output: [7,6,-1,4,6]
Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7].
In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6].
In the third query, Alice cannot meet Bob since Bob cannot move to any other building.
In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4].
In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6].
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.
Constraints:
- 1 <= heights.length <= 5 * 104
- 1 <= heights[i] <= 109
- 1 <= queries.length <= 5 * 104
- queries[i] = [ai, bi]
- 0 <= ai, bi <= heights.length - 1
항상 사람을 괴롭히는 Alice와 Bob이다.
딱 봐도 쉽지 않아 보이는 문제지만, 일단 try는 해보기
뭔가 문제 Description을 읽어보면 할만할 거 같은데, 또 time limit에 걸릴 거 같긴하다..
1. Python
역시나.. 가벼운 test case는 다 풀었는데, 이상한 곳에서 Wrong Answer이 떴다. 뭐고 이거
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
ans = []
# O(n^2 sol..)
for i in range(len(queries)):
# low & high are index
high = max(queries[i])
low = min(queries[i])
if heights[high] >= heights[low] :
ans.append(high)
continue
else:
cond = False
for j in range(high+1,len(heights)):
if heights[j] > heights[low] and heights[j] > heights[high]:
cond = True
ans.append(j)
break
if not cond :
ans.append(-1)
return ans
뭔가 Naive하게 잘 풀릴 거 같은데, Time limit이 뜨는 것들은 다 이유가 있다.
괜히 Hard난이도 문제가 아님..
근데 어떻게 시간효율을 줄일 수 있을까
솔직히 for 문 2개 겹쳐서 쓸 때부터 위 결과는 예상했다.
답을 찾아봤는데,, 이것들 뭐냐..
from bisect import bisect_left
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
n = len(heights)
st = [[0] * 20 for _ in range(n)]
Log = [-1] * (n + 1)
Log[0] = -1
for i in range(1, n + 1):
Log[i] = Log[i >> 1] + 1
for i in range(n):
st[i][0] = heights[i]
for i in range(1, 20):
for j in range(n):
if j + (1 << i) <= n:
st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1])
def Ask(l, r):
k = Log[r - l + 1]
return max(st[l][k], st[r - (1 << k) + 1][k])
res = []
for l, r in queries:
if l > r:
l, r = r, l
if l == r:
res.append(l)
continue
if heights[r] > heights[l]:
res.append(r)
continue
max_height = max(heights[r], heights[l])
left, right = r + 1, n
while left < right:
mid = (left + right) // 2
if Ask(r + 1, mid) > max_height:
right = mid
else:
left = mid + 1
res.append(left if left != n else -1)
return resclass Solution:
def leftmostBuildingQueries(self, heights, queries):
n, q = len(heights), len(queries)
result = [-1] * q
deferred = [[] for _ in range(n)]
pq = []
# 작은 수 a , 큰 수 b
for i in range(q):
a, b = queries[i]
if a > b:
a, b = b, a
if a == b or heights[a] < heights[b]:
result[i] = b
else:
deferred[b].append((heights[a], i))
# 얘가 이해가 안 간다..
for i in range(n):
for query in deferred[i]:
heapq.heappush(pq, query)
while pq and pq[0][0] < heights[i]:
result[pq[0][1]] = i
heapq.heappop(pq)
return result
heap을 쓰는 건 조금 이해가 가긴 한다.
다시 보니 이해가 안 간다..
뒤에 for문에서 deferred를 건져내는 부분을 내가 과연 생각해낼 수 있을까 싶다.
코드를 대놓고 봐도 어려운데;;
ㅠㅠ
2. C++
// #C++
class Solution {
public:
int n, sparseTable[50010][20], logValues[50010];
int queryMaximum(int left, int right) {
int k = logValues[right - left + 1];
return max(sparseTable[left][k], sparseTable[right - (1 << k) + 1][k]);
}
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
int n = heights.size();
sparseTable[n][0] = 2e9;
logValues[0] = -1;
for (int i = 1; i <= n; i++) {
logValues[i] = logValues[i >> 1] + 1;
}
for (int i = 0; i < n; i++) {
sparseTable[i][0] = heights[i];
}
for (int i = 1; i < 20; i++) {
for (int j = 0; j + (1 << i) - 1 <= n; j++) {
sparseTable[j][i] = max(sparseTable[j][i - 1], sparseTable[j + (1 << (i - 1))][i - 1]);
}
}
int numQueries = queries.size();
vector<int> results(numQueries);
for (int queryIndex = 0; queryIndex < numQueries; queryIndex++) {
int left = queries[queryIndex][0], right = queries[queryIndex][1];
if (left > right) swap(left, right);
if (left == right) {
results[queryIndex] = left;
continue;
}
if (heights[right] > heights[left]) {
results[queryIndex] = right;
continue;
}
int maxHeight = max(heights[right], heights[left]);
int low = right, high = n, mid;
while (low < high) {
mid = (low + high) >> 1;
if (queryMaximum(right, mid) > maxHeight) {
high = mid;
} else {
low = mid + 1;
}
}
results[queryIndex] = (low == n) ? -1 : low;
}
return results;
}
};
C++ heap으로 풀면 아래와 같다
min-heap
#include <vector>
#include <queue>
#include <utility>
using namespace std;
class Solution {
public:
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
int n = heights.size();
int q = queries.size();
vector<int> result(q, -1);
vector<vector<pair<int, int>>> deferred(n); // 각 빌딩별 처리해야 할 쿼리 저장
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 최소 힙
// 1. 쿼리 분류
for (int i = 0; i < q; ++i) {
int a = queries[i][0];
int b = queries[i][1];
if (a > b) swap(a, b); // 항상 a <= b 유지
if (a == b || heights[a] < heights[b]) {
result[i] = b; // 바로 만날 수 있는 경우
} else {
deferred[b].emplace_back(heights[a], i); // deferred[b]에 쿼리 저장
}
}
// 2. 빌딩 순회
for (int i = 0; i < n; ++i) {
// 현재 빌딩에서 처리해야 할 쿼리를 힙에 추가
for (auto& query : deferred[i]) {
pq.push(query); // (Alice의 높이, 쿼리 인덱스)
}
// 힙에서 조건을 만족하는 쿼리를 처리
while (!pq.empty() && pq.top().first < heights[i]) {
result[pq.top().second] = i; // 현재 빌딩에서 Alice와 Bob이 만날 수 있음
pq.pop();
}
}
return result;
}
};