8주차 일요일 1 1 - LeetCode-Study-Team/solutions GitHub Wiki
A university has admitted a group of n students with varying skill levels. To better accommodate the students, the university has decided to create classes tailored to the skill levels. A placement examination will return a skill level that will be used to group the students, where levels[i] represents the skill level of student i. All students within a group must have a skill level within maxSpread, a specified range of one another. Determine the minimum number of classes that must be formed.
Example
인풋: levels = [1, 4, 7, 3, 4] 이랑 maxSpread = 2
답: 3
The students in any group must be within maxSpread = 2 levels of each other. In this case, one optimal grouping is (1, 3), (4, 4), and (7). Another possible grouping is (1), (3, 4, 4), (7). There is no way to form fewer than 3 groups.
Constraints
- 1 ≤ n ≤ 105
- 1 ≤ levels[i] ≤ 109 for every i (where 0 ≤ i ≤ n-1)
- 0 ≤ maxSpread ≤ 109
- Greedy 알고리즘
- the problem-solving heuristic of making the locally optimal choice at each stage.
public static int groupDivision(List<Integer> levels, int maxSpread) {
Collections.sort(levels);
if (levels.isEmpty()) {
return 0;
}
int left = levels.get(0);
int groupCount = 1;
for (int right = 0; right < levels.size(); right++) { // 5번
if (levels.get(right) - left > maxSpread) {
groupCount++;
left = levels.get(right);
}
}
return groupCount;
}A forklift worker moves products from one place to the other in an automotive parts warehouse. There a map in the dashboard that shows, in real time, the open and blocked sections inside the warehouse. The map is displayed as an n x m matrix of 1's and 0's which represent open and blocked sections respectively. A forklift driver always starts at the upper left corner of the map at warehouse[0][0] and tries to reach the bottom right section of the map or warehouse[n-1][m-1]. Each movement must be in increasing value along a row or column but not both. Given the warehouse map, determine the number of distinct paths to get from warehouse[0][0] to warehouse[n-1][m-1]. The number may be large, so return the value modulo (109+7).
Example
인풋: warehouse = [1, 1, 0, 1], [1, 1, 1, 1]
답: 2
The matrix below is drawn from the warehouse array showing open and blocked sections of the warehouse. 1 indicates an open section and 0 indicates a blocked section. It is only possible to travel through open sections, so no path can go through the section at (0, 2).
There are 2 possible paths from warehouse[0][0] to warehouse[1][3].
Constraints
- 1 ≤ n, m ≤ 1000
- Each cell in matrix a contains either a 0 or a 1.
public int numPaths(List<List<Integer>> warehouse) {
if (warehouse.isEmpty()) {
return 0;
}
// 첫번째 값이 0 이면, 끝에 도달 불가
if (warehouse.get(0).get(0) == 0) {
return 0;
}
int n = warehouse.size();
int m = warehouse.get(0).size();
int[][] dp = new int[n][m];
dp[0][0] = warehouse.get(0).get(0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0) {
continue;
}
if (i == 0) {
// 전의 위치를
if (warehouse.get(i).get(j) == 0 || dp[i][j - 1] == 0) { // {0, 1} {0, 2} 등등
dp[i][j] = 0;
continue;
} else {
dp[i][j] = 1;
continue;
}
}
if (j == 0) { // {1, 0} {2, 0} 등등
if (warehouse.get(i).get(j) == 0 || dp[i - 1][j] == 0) {
dp[i][j] = 0;
continue;
} else {
dp[i][j] = 1;
continue;
}
}
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
for (int[] a : dp) {
System.out.println(Arrays.toString(a));
}
return dp[n - 1][m - 1];
}Sample
인풋: (A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)
답: (A(B(D)(G))(C(E(F))(H)))
Explanation
A binary tree is represented as a sequence of parent-child pairs, for example:
(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)
A tree with those edges may be illustrated in many ways. Here are two:
The following is a recursive definition for the S-expression of a tree:
S-exp(node) = ( node->val (S-exp(node->first_child))(S-exp(node->second_child))), if node != NULL = "", node == NULL
where, first_child->val < second_child->val (first_child->val is lexicographically smaller than second_child-> val)
This tree can be represented in an S-expression in multiple ways. The lexicographically smallest way of expressing it is as follows:
(A(B(D)(G))(C(E(F))(H)))
Translate the node-pair representation into its lexicographically smallest S-expression or report any errors that do not conform to the definition of a binary tree.
The list of errors with their codes is as follows:
Error Code Type of error E1 More than 2 children E2 Duplicate Edges E3 Cycle present (node is direct descendant of more than one node) E4 Multiple roots E5 Any other error
Function Description
public static String sExpression(String nodes) {
return;
}- Complete the function sExpression in the editor below. The function must return either the lexicographically lowest S-expression or the lexicographically lowest error code as a string.
- sExpression has the following parameter(s):
- nodes: a string of space-separated parenthetical elements, each of which contains the names of two connected nodes separated by a comma
Constraints:
All node names are single characters in the range ascii[A-Z]
- The maximum node count is 26.
- There is no specific order to the input (parent, child) pairs.
If you have not worked with trees when programming before then the following may be helpful. A tree can be stored in memory as a map from parents to each of their children. For example, if { K: V } indicates an item in a dictionary or hashmap with key K and value V, and [X, Y] indicates a list or array with elements X and Y, then the example tree could be stored as:
{ A: [B, C] B: [D, G] C: [E, H] D: [] E: [F] F: [] G: [] H: [] }
This is not the only way to store a tree, nor is it necessarily the best way in all cases, however it will be sufficient to solve the problem given to you.
public static void main(String[] args) {
String input = "(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)";
Character root = null;
Map<Character, List<Character>> adjList = new HashMap<>();
Map<Character, Integer> numParents = new HashMap<>(); // numParents.get('C')
//E1 - Invalid input formart (missing symbols, more than one blank space as pair separators)
//E2 - Duplicate (Parent, Child) pairs
//E3 - Invalid binary tree (parent has 2 > children)
//E4 - Input contains a forest (multiple root nodes)
//E5 - Input contain cycles within the tree (ex: child's child = parent)
int i = 0;
while (i < input.length() -2) {
// (A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)
while (i < input.length() && (input.charAt(i) < 'A' || input.charAt(i) > 'Z') ) i++;
Character parent = input.charAt(i++);
if (!Character.isLetter(parent)) {
System.out.println("E1");
return;
}
while (i < input.length() && (input.charAt(i) < 'A' || input.charAt(i) > 'Z') ) i++;
Character child = input.charAt(i++);
if (!Character.isLetter(child)) {
System.out.println("E1");
return;
}
if (adjList.get(parent) == null) { // A
adjList.put(parent, new ArrayList<Character>());
}
if (adjList.get(child) == null) { // B
adjList.put(child, new ArrayList<Character>());
}
for (int j = 0; j < adjList.get(parent).size(); j++) {
if (adjList.get(parent).get(j) == child) {
System.out.println("E2"); //If there is already such a parent/child pair
return;
}
}
if (adjList.get(parent).size() == 2) {
System.out.println("E3"); // If parent node already has 2 child
return;
}
numParents.put(child, numParents.getOrDefault(child, 0) + 1); // A - >
numParents.put(parent, numParents.getOrDefault(parent, 0));
if (numParents.get(child) > 1) {
System.out.println("E5"); //If node has 2 parents already
return;
}
adjList.get(parent).add(child);
}
int numRoots = 0;
Iterator<Character> keys = numParents.keySet().iterator();
while(keys.hasNext()) {
Character parent = keys.next();
if ( numParents.get(parent)== 0) {
root = parent;
numRoots++;
}
if (numRoots > 1) {
System.out.println("E4");
return;
}
}
printTraverse(adjList, root);
}
private static void printTraverse(Map<Character, List<Character>> adjList, Character root) {
System.out.print("(" + root);
int numChild = adjList.get(root).size();
if (numChild == 1) {
printTraverse(adjList, adjList.get(root).get(0));
} else if (numChild == 2) {
if (adjList.get(root).get(0) < adjList.get(root).get(1)) {
printTraverse(adjList, adjList.get(root).get(0));
printTraverse(adjList, adjList.get(root).get(1));
} else {
printTraverse(adjList, adjList.get(root).get(1));
printTraverse(adjList, adjList.get(root).get(0));
}
}
System.out.print(")");
}