9주차 일요일 1 1 - LeetCode-Study-Team/solutions GitHub Wiki
An Amazon seller is celebrating ten years in business! They are having a sale to honor their privileged members, those who have purchased from them in the past five years. These members receive the best discounts indicated by any discount tags attached to the product. Determine the minimum cost to purchase all products listed. As each potential price is calculated, round it to the nearest integer before adding it to the total. Return the cost to purchase all items as an integer.
There are three types of discount tags :
- Type 0: discounted price, the item is sold for a given price.
- Type 1: percentage discount, the customer is given a fixed percentage discount from the retail price.
- Type 2: fixed discount, the customer is given a fixed amount off from the retail price.
Example
products = [['10', 'd0', 'd1'] , ['15', 'EMPTY', 'EMPTY'] , ['20', 'd1', 'EMPTY']]*
*discounts = [['d0','1','27'], ['d1', '2', '5']]*
The products array elements are in the form ['price', 'tag 1', 'tag 2', ..., 'tag m-1']. There may be zero or more discount codes associated with a product. Discount tags in the products array may be 'EMPTY' which is the same as a null value. The discounts array elements are in the form ['tag', 'type', 'amount'].
-
If a privileged member buys product
1 listed at a price of 10
with two discounts available:
- Under discount d0 of type 1, the discounted price is 10 - 10 * 0.27 = 7.30, round to 7.
- Under discount d1 of type 2, the discounted price is 10 - 5 = 5.
- The price to purchase the product 1 is the lowest of the two, or 5 in this case
-
The second product is priced at 15 because there are no discounts available
-
The third product is priced at 20. Using discount tag d1 of type 2 , the discounted price is 20 - 5 = 15
The total price to purchase the three items is 5 + 15 + 15 = 35.
Notes: Not all items will have the maximum number of tags. Empty tags may just not exist in input, or they may be filled with the string EMPTY. These are equivalent as demonstrated in the example above.
Function Description
Complete the function findLowestPrice in the editor below.
findLowestPrice has the following parameter(s):
[string] products[n][m]: a 2D array of product descriptors as strings: price followed by up to m-1 discount tags
[string] discounts[d][3]: a 2D array of tag descriptors as strings: tag, type, amount
Returns:
int*: the total amount paid for all* listed products, discounted to privileged members' pricing
Constraints
- 1 ≤ n, m, d ≤ 1000
Input Format For Custom Testing
The first line contains an integer, n, the size of the array products.The next line contains an integer, m, the number of elements in each products[i].Each line i of the n subsequent lines (where 0 ≤ i < n) contains an array of strings describing the product details: price followed by applicable discount tags, or EMPTY.The next line contains an integer, d, the size of the array discounts.The next line contains an integer, 3, denoting the count of the attributes of each discount. Each line j of the d subsequent lines (where 0 ≤ j < d) contains an array of strings describing the discount details.
Sample Case 0
List<List<String>> products2 = List.of(List.of("10", "sale", "january-sale"), List.of("200", "sale", "EMPTY"));
List<List<String>> discounts2 = List.of(List.of("sale", "0", "10"), List.of("january-sale", "1", "10"));
System.out.println(problem1.findLowestPrice(products2, discounts2)); // 9+10 = 19Explanation
- If a privileged member buys product 1 listed at a price of 10 with two discounts available:
- Under discount 'sale' of type 0, the item is sold for a given price 10
- Under discount 'january-sale' of type 1, the discounted price is 10 - 0.1*10 = 9
- The price to purchase the product 1 is the lowest of the two, or 9 in this case
- The second product is priced at 200. Using 'sale' of type 0, the item is sold for a given price 10
Code
public static int findLowestPrice(List<List<String>> products, List<List<String>> discounts) {
}package Amazon;
import java.util.*;
public class Problem1 {
public static void main(String[] args) {
Problem1 problem1 = new Problem1();
List<List<String>> products1 = List.of(List.of("10", "d0", "d1"),
List.of("15", "EMPTY", "EMPTY"), List.of("20", "d1", "EMPTY"));
List<List<String>> discounts1 = List.of(List.of("d0", "1", "27"),
List.of("d1", "2", "5"));
System.out.println(problem1.findLowestPrice(products1, discounts1)); // 5 + 15 + 15 = 35
List<List<String>> products2 = List.of(List.of("10", "sale", "january-sale"), List.of("200", "sale", "EMPTY"));
List<List<String>> discounts2 = List.of(List.of("sale", "0", "10"), List.of("january-sale", "1", "10"));
System.out.println(problem1.findLowestPrice(products2, discounts2)); // 9+10 = 19
}
public static int findLowestPrice(List<List<String>> products, List<List<String>> discounts) {
int[] minCosts = new int[products.size()];
Map<String, List<Integer>> discountMap = createDiscountMap(products, discounts);
for (int i = 0; i < products.size(); i++) {
List<String> oneProduct = products.get(i);
minCosts[i] = findMinCost(oneProduct, discountMap);
}
System.out.println(Arrays.toString(minCosts));
return calculateTotalCost(minCosts);
}
private static Map<String, List<Integer>> createDiscountMap(List<List<String>> products, List<List<String>> discounts) {
// key: product, value: price
Map<String, List<Integer>> discountMap = new HashMap<>();
for (int i = 0; i < discounts.size(); i++) {
List<String> d = discounts.get(i);
String key = d.get(0);
discountMap.put(key, new ArrayList<>());
for (int j = 1; j < d.size(); j++) {
discountMap.get(key).add(Integer.parseInt(d.get(j)));
}
}
return discountMap;
}
private static int findMinCost(List<String> eachProduct, Map<String, List<Integer>> discountMap) {
int originPrice = Integer.parseInt(eachProduct.get(0));
int min = originPrice;
// - Type 0: discounted price, the item is sold for a given price.
// - Type 1: percentage discount, the customer is given a fixed percentage discount from the retail price.
// - Type 2: fixed discount, the customer is given a fixed amount off from the retail price.
int discountType;
int amount;
for (int i = 1; i < eachProduct.size(); i++) {
String tag = eachProduct.get(i);
if (tag.equals("EMPTY")) {
continue;
}
discountType = discountMap.get(tag).get(0);
amount = discountMap.get(tag).get(1);
// 할인 제도가 어떤 지에 따라
switch (discountType) {
case 0:
min = Math.min(min, amount);
break;
case 1:
min = Math.min(min, Math.round(originPrice * ((float) (100 - amount) / 100)));
break;
case 2:
min = Math.min(min, originPrice - amount);
break;
}
}
return min;
}
private static int calculateTotalCost(int[] minCosts) {
return Arrays.stream(minCosts).sum();
}
}Amazon Web Services (AWS) is working on a new security feature to help encode text. Consider a string that consists of lowercase English alphabetic letters (i.e., [a-z]) only. The following rules are used to encode all of its characters into string s:
- a is encoded as 1, b is encoded as 2, c is encoded as 3, …, and i is encoded as 9.
- j is encoded as 10#, k is encoded as 11#, l is encoded as 12#, …, and z is encoded as 26#.
- If there are two or more consecutive occurrences of any character, then the character count is written within parentheses (i.e., (c), where c is an integer denoting the count of consecutive occurrences being encoded) immediately following the encoded character. For example, consider the following string encodings:
- String "abzx" is encoded as s = "1226#24#".
- String "aabccc" is encoded as s = "1(2)23(3)".
- String "bajj" is encoded as s = "2110#(2)".
- String "wwxyzwww" is encoded as s = "23#(2)24#25#26#23#(3)".
Given an encoded string s, determine the character counts for each letter of the original, decoded string. Return an integer array of length 26 where index 0 contains the number of 'a' characters, index 1 contains the number of 'b' characters and so on.
Function Description
Complete the frequency function in the editor below. It should return an array of 26 integers as described.
frequency has the following parameter:
s: an encoded string
Constraints
- String s consists of decimal integers from 0 to 9, #'s, and ()'s only.
- 1 ≤ length of s ≤ 105
- It is guaranteed that string s is a valid encoded string.
- 2 ≤ c ≤ 104, where c is a parenthetical count of consecutive occurrences of an encoded character.
Input Format For Custom Testing
Input Format For Custom TestingInput from stdin will be processed as follows and passed to the function. The only line contains the string s, the encoded string.
Sample Case 0
Input: 1226#24#
Output: 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
Sample Case 1
Input: 1(2)23(3)
Output: 2 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Case 2
Input: 2110#(2)
Output: 1 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Case 3
Input: 23#(2)24#25#26#23#(3)
Output: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1
Code
public static List<Integer> frequency(String s) {
}public class Problem2 {
public static void main(String[] args) {
Problem2 problem2 = new Problem2();
System.out.println(problem2.frequency2("2110#(2)")); // 1 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
System.out.println(problem2.frequency2("23#(2)24#25#26#23#(3)")); // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1
System.out.println(problem2.frequency2("1226#24#")); // 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
System.out.println(problem2.frequency2("1(2)23(3)")); // 2 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
System.out.println(problem2.frequency2("2110#(2)")); // 1 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
System.out.println(problem2.frequency2("23#(2)24#25#26#23#(3)")); // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1
System.out.println(problem2.frequency2("21(2)10#(102)")); // [2, 1, 0, 0, 0, 0, 0, 0, 0, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
}
public static List<Integer> frequency2(String s) {
List<Integer> result = new ArrayList<>(Collections.nCopies(26, 0));
StringBuilder twoDigitsSB = new StringBuilder();
StringBuilder repeatCntSB = new StringBuilder();
int repeatCnt = 0;
for (int right = s.length() - 1; right >= 0; --right) {
if (s.charAt(right) == ')') {
right--;
while (s.charAt(right) != '(') {
repeatCntSB.append(s.charAt(right));
right--;
}
right--;
repeatCnt = Integer.parseInt(repeatCntSB.reverse().toString());
}
int alphaLoc; // 알파벳 위치
if (s.charAt(right) == '#') {
twoDigitsSB.insert(0, s.charAt(--right));
twoDigitsSB.insert(0, s.charAt(--right));
alphaLoc = Integer.parseInt(twoDigitsSB.toString()) - 1;
twoDigitsSB.setLength(0);
} else {
alphaLoc = Character.getNumericValue(s.charAt(right)) - 1;
}
if (repeatCntSB.length() == 0) {
result.set(alphaLoc,
result.get(alphaLoc) + 1);
} else {
result.set(alphaLoc,
result.get(alphaLoc) + repeatCnt);
repeatCntSB.setLength(0);
}
}
return result;
}