Heap 1문제, DFS 2문제를 풀었다. 문제가 어려워지면서 푸는 데에 시간이 들기도 하고 답을 유추하는 과정이 복잡해지니 포스팅도 소홀해지기 시작했다... 😅 그리고 문제를 풀고 몰아서 포스팅을 쓰려고 하니까 어떻게 풀었는지 기억나지 않는 경우도 많은 것 같다. 문제를 풀 때 어떤 아이디어로 접근했는지 기록해 두면 다시 봤을 때 도움이 될 것 같다.
2542. Maximum Subsequence Score
길이가 n인 배열 num1, num2가 주어지고, 양수 k가 주어졌다. num1 배열에서 k 개의 인덱스를 선택했을 때, 스코어는 선택된 nums1의 요소 합 * nums2의 선택된 요소 중 최소값이다. 이 스코어의 최댓값을 구하라.
You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.
For chosen indices i0, i1, ..., ik - 1, your score is defined as:
- The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
- It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).
Return the maximum possible score.
A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.
문제의 설명을 읽고 조금 멍해졌지만, nums2의 선택된 값들 중 최소값을 곱해야 하기 때문에 불필요한 연산을 피하려면 정렬이 필요할 것 같다고 생각했다. 그런데 num1과 num2를 함께 정렬해야 해서 인덱스 배열을 만들어서 정렬해야 하나 고민했는데, 솔루션(ㅠㅠ)을 보니 간단히 이중 배열을 만들어서 정렬을 했다! 문제를 풀었어도 솔루션이나 다른 사람의 답을 보는 게 이렇게 아이디어를 줄 때가 있어서 보는 게 좋다.
오름차순으로 정렬하고 내가 nums2의 i번째 값을 선택했다고 하면, nums1에서 0~i 중 가장 큰 값 k개를 선택하면 최대값을 만들 수 있다. 이때 사용할 수 있는 자료구조가 최소힙이다. 최소힙의 크기를 k개로 유지하면서, i를 이동할 때마다 가장 작은 값을 빼고 nums1[i]를 추가한다면 nums1의 최댓값을 빠르게 계산할 수 있다.
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int n = nums2.length;
int[][] pairs = new int[n][2];
for(int i=0; i<n; i++) {
pairs[i] = new int[]{nums1[i], nums2[i]};
}
Arrays.sort(pairs, (a, b) -> b[1] - a[1]);
PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> a - b);
long topKSum = 0;
for(int i=0; i<k; i++) {
topKSum += pairs[i][0];
pq.offer(pairs[i][0]);
}
long ret = topKSum * pairs[k-1][1];
for (int i=k; i < n; i++) {
int minValue = pq.poll();
topKSum += pairs[i][0] - minValue;
pq.offer(pairs[i][0]);
ret = Math.max(ret, topKSum * pairs[i][1]);
}
return ret;
}
}시간복잡도는 처음에 pairs를 만들 때 O(n), pairs를 정렬할 때 O(nlogn)이다. 그리고 pair를 순회하면서 최소힙 pq에서 원소를 삭제, 추가하고 있다(O(logk)). O(n(1 + logn + logk)) 이고 k <= n 이기 때문에 최종 시간복잡도는 O(nlogn)이다.
공간복잡도는 pairs 배열 O(2n), 자바의 정렬 메소드를 실행할 때 O(logn), 최소힙 O(k)가 필요하다. 최종 공간복잡도는 O(n)이 된다.
자바의 정렬 메소드에 추가 공간이 O(logn)이 필요하다는 사실은 이번에 처음 알게 된 것 같다. 추가적으로 확인이 필요할 듯
399. Evaluate Division
수식이 들어있는 배열과 실수값이 든 배열이 주어졌다. 각 수식은 2자리 배열이며 equations[i] = [Ai, Bi] 는 Ai / Bi 수식을 의미하고, values[i]는 이 수식의 값을 의미한다. 그리고 queries 배열에 수식 queries[j] = [Cj, Dj] 가 주어졌을 때 수식의 값을 찾아야 한다. 만약 수식 값을 구할 수 없다면 -1.0을 리턴한다.
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.
이것도 솔루션을 참고했는데😭, 아이디어는 equation의 숫자를 노드로, value를 에지 값으로 인식하는 것부터 해야한다. 나는 A/B를 하나의 값으로 보고 가능한 모든 조합을 만들고 값을 계산해서 저장해야 한다고 생각했는데, 분자 -> 분모 관계를 그래프로 만들면 계산하고자 하는 query 값을 노드 경로를 따라가면서 엣지 값을 곱하면 구할 수 있다.
먼저 그래프를 만드는데 분자 -> 분모도 생성하고 분모 -> 분자도 생성한다. 그리고 query값을 구하기 위해 그래프를 bfs로 순회한다. 만약 분모 노드까지 찾아가지 못한다면 -1.0을 리턴한다.
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
double[] ret = new double[queries.size()];
Map<String, List<Pair<String, Double>>> graph = new HashMap<>();
for(int i=0; i<equations.size(); i++) {
List<String> equ = equations.get(i);
String dividend = equ.get(0);
String divisor = equ.get(1);
List<Pair<String, Double>> adjcents = graph.getOrDefault(dividend, new ArrayList<>());
adjcents.add(new Pair<>(divisor, values[i]));
graph.put(dividend, adjcents);
adjcents = graph.getOrDefault(divisor, new ArrayList<>());
adjcents.add(new Pair(dividend, 1.0 / values[i]));
graph.put(divisor, adjcents);
}
for(int i=0; i<queries.size(); i++) {
List<String> query = queries.get(i);
String dividend = query.get(0);
String divisor = query.get(1);
if (!graph.containsKey(dividend) || !graph.containsKey(divisor)) {
ret[i] = -1.0;
} else {
ret[i] = bfs(dividend, divisor, graph);
}
}
return ret;
}
private double bfs(String start, String end, Map<String, List<Pair<String, Double>>> graph) {
Queue<Pair<String, Double>> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(new Pair<>(start, 1.0));
visited.add(start);
while(!q.isEmpty()) {
Pair<String, Double> pair = q.poll();
if (pair.getKey().equals(end)) {
return pair.getValue();
}
for(Pair<String, Double> adj : graph.get(pair.getKey())) {
if (!visited.contains(adj.getKey())) {
visited.add(adj.getKey());
q.offer(new Pair<>(adj.getKey(), adj.getValue() * pair.getValue()));
}
}
}
return -1.0;
}
}시간 복잡도는 변수의 개수를 l, equations의 크기를 n, queries의 크기를 m이라고 했을 때, 그래프 생성에 O(2n), 그리고 쿼리를 순회하면서 생성된 그래프를 방문하기 때문에 O(m * l)이 소요된다. 따라서 시간 복잡도는 O(n + m * l)이 된다.
공간 복잡도의 경우 그래프 저장에 O(n)가 필요해서 O(n)이다.
1466. Reorder Routes to Make All Paths Lead to the City Zero
0부터 n-1로 매겨진 n개의 도시에는 서로 다른 두 도시 사이에 오직 하나의 길이 있다. 각 도시에서 도시 0을 방문할 수 있도록 에지의 방향을 바꾼다고 할 때 최소한의 엣지 변경 개수를 구하라.
There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.
It's guaranteed that each city can reach city 0 after reorder.
이 문제는 다행히 힌트만 보고 풀었다! 😁 힌트는 이 트리(그래프)를 undirected 그래프로 보고 0번째 노드부터 노드를 순회하면서 방향을 바꿔야 하는 경우를 찾으라는 것이었다. 힌트를 듣고 나니 바로 감이 왔는데, undirected 그래프인 것처럼 edgeMap을 만들면서도 어떻게 방향을 바꿔야 하는 경우도 함께 저장할 수 있을지 고민했다. 그래서 고민하다가 Edge라는 타입을 만들어서 엣지가 정방향인지, 역방향인지 함께 저장했다. 주의할 점이라면 0번째 도시로 가는게 아닌, 0번째 도시에서 나머지 다른 도시로 가는 것이기 때문에 여기서 정방향인 엣지가 내가 바꿔야하는 에지인 것이다.
class Solution {
public int minReorder(int n, int[][] connections) {
int[] ret = new int[1];
boolean[] visited = new boolean[n];
Map<Integer, List<Edge>> edgeMap = new HashMap<>();
for(int i=0; i<n-1; i++) {
int[] edge = connections[i];
List<Edge> edges = edgeMap.getOrDefault(edge[0], new ArrayList<>());
edges.add(new Edge(edge[1], false));
edgeMap.put(edge[0], edges);
List<Edge> revEdges = edgeMap.getOrDefault(edge[1], new ArrayList<>());
revEdges.add(new Edge(edge[0], true));
edgeMap.put(edge[1], revEdges);
}
visited[0] = true;
dfs(0, edgeMap, visited, ret);
return ret[0];
}
class Edge {
int node;
boolean rev;
public Edge(int node, boolean rev) {
this.node = node;
this.rev = rev;
}
}
private void dfs(int cur, Map<Integer, List<Edge>> edgeMap, boolean[] visited, int[] ret) {
List<Edge> edges = edgeMap.getOrDefault(cur, new ArrayList<>());
for(Edge edge : edges) {
if (!visited[edge.node]) {
visited[edge.node] = true;
if (!edge.rev) {
ret[0]++;
}
dfs(edge.node, edgeMap, visited, ret);
}
}
}
}edgeMap을 만들 때 O(n-1), dfs로 순회할 때 O(n)이므로 시간 복잡도는 O(n)이다.
공간 복잡도는 edgeMap을 만들 때 O(n-1), dfs를 실행할 때 스택 O(n)때문에 O(n)이다.
