π νλ‘κ·Έλλ¨Έμ€ / ν΄μ / Level2 / μμ₯
π λ¬Έμ
νλ‘κ·Έλλ¨Έμ€
μ½λ μ€μ¬μ κ°λ°μ μ±μ©. μ€ν κΈ°λ°μ ν¬μ§μ λ§€μΉ. νλ‘κ·Έλλ¨Έμ€μ κ°λ°μ λ§μΆ€ν νλ‘νμ λ±λ‘νκ³ , λμ κΈ°μ κΆν©μ΄ μ λ§λ κΈ°μ λ€μ λ§€μΉ λ°μΌμΈμ.
programmers.co.kr
π« μ ν μ¬ν
- clothesμ κ° νμ [μμμ μ΄λ¦, μμμ μ’ λ₯]λ‘ μ΄λ£¨μ΄μ Έ μμ΅λλ€.
- μ€νμ΄κ° κ°μ§ μμμ μλ 1κ° μ΄μ 30κ° μ΄νμ λλ€.
- κ°μ μ΄λ¦μ κ°μ§ μμμ μ‘΄μ¬νμ§ μμ΅λλ€.
- clothesμ λͺ¨λ μμλ λ¬Έμμ΄λ‘ μ΄λ£¨μ΄μ Έ μμ΅λλ€.
- λͺ¨λ λ¬Έμμ΄μ κΈΈμ΄λ 1 μ΄μ 20 μ΄νμΈ μμ°μμ΄κ³ μνλ²³ μλ¬Έμ λλ '_' λ‘λ§ μ΄λ£¨μ΄μ Έ μμ΅λλ€.
- μ€νμ΄λ ν루μ μ΅μ ν κ°μ μμμ μ μ΅λλ€.
π μ μΆλ ₯ μ
| clothes | return |
| [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] | 5 |
| [["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]] | 3 |
π€ νμ΄ λ°©λ²
1οΈβ£ λ°©λ² (1) : Map μΌλ‘ μ’ λ₯λ³ κ°μ νμΈ ν μ‘°ν© μ¬μ©
β μ¬κ³ κ³Όμ
/*
νμ΄ λ°©λ²
(1) λ³μ
a) Map -> key : (String) μ’
λ₯ / value : (int) κ°μ
(2) μ’
λ₯ νμ
-> key
a) split("_") μν
κ°) 첫λ²μ§Έ μμ : μ΄λ¦
λ) λλ²μ¨° μμ : μ’
λ₯
b) a-λ) μ μ’
λ₯κ° key μ μλμ§ νμΈ (if λ¬Έ)
κ°) true : κ°μ ++ ν΄μ μ
λ°μ΄νΈ
λ) false : κ°μ 1λ‘ ν΄μ μΆκ° (add)
(3) κ²½μ°μ μ νμ°
a) value set λ°ν
b) max κ° νμΈ
c) 1-max κΉμ§ κ²½μ°μ μ νμΈ
ex) λͺ¨μ : 2κ°, μ κΈλΌμ€ : 1κ°, λ°μ§ 2κ°
κ°) max : 2κ°
λ) 1κ°μ κ²½μ° : 2 + 1 + 2 = 5
λ€) 2κ°μ κ²½μ° : 2 * 1 + 2 * 2 + 1 * 2 = 8
β‘οΈ μ‘°ν©μΌλ‘ κ°μΌνλ€. / μμ±λ λ λ§λ€ κ³±μ answer μ λνλ λ°©μ
*/
β‘οΈ μμ : μλμ κ°μ΄ μ’ λ₯λ³λ‘ κ°μλ₯Ό νμΈνμ¬ μ‘°ν©μ ꡬνκ³ μ νλ€.
μ£Όμ΄μ§ λ°°μ΄ : [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]
μμ±λ Map νν β‘οΈ entrySet() νΈμΆμ
[eyewear=1, headgear=2]
①ꡬν μ½λ
import java.util.Map;
import java.util.Set;
import java.util.HashMap;
class Solution {
public static int[] counts;
public static int answer = 0;
public int solution(String[][] clothes) {
// Map μμ±
Map<String, Integer> map = new HashMap<>();
// λ°°μ΄ λΆλ¦¬
for (String[] clothe : clothes) {
String type = clothe[1];
// map μ μ½μ
int count = 0;
if (map.containsKey(type)) {
count = map.get(type);
}
map.put(type, ++count);
}
// // μ μμ μΌλ‘ λ΄κ²Όλμ§ νμΈ
// System.out.println(map.entrySet());
// κ²½μ°μ μ νμΈ (1)
String[] types = map.keySet().toArray(new String[map.size()]);
counts = new int[map.size()];
for (int i=0; i<types.length; i++) {
counts[i] = map.get(types[i]);
}
// κ²½μ°μ μ νμΈ (2) μ‘°ν©
for (int r=1; r <= counts.length; r++) {
Comb(new boolean[counts.length], 0, r, 1);
System.out.println(r);
}
return answer;
}
// μ‘°ν©
public static void Comb (boolean[] visited, int start, int r, int total) {
if (r==0) {
answer += total;
return;
}
for (int i=start; i<counts.length; i++) {
// λ°©λ¬Έ
visited[i] = true;
total *= counts[i];
// μ¬κ·
Comb(visited, i+1, r-1, total);
// 볡ꡬ
total /= counts[i];
visited[i] = false;
}
}
}
β’ κ²°κ³Ό

β‘οΈ 30κ°μ ν μ€νΈ μ€ 29κ°λ₯Ό ν΅κ³Όνκ³ 1κ°λ₯Ό μκ°μ΄κ³Όλ‘ μ€ν¨νμλ€. νμΈν΄λ³΄λ 첫λ²μ§Έ ν μ€νΈλ μλ‘ λ€λ₯Έ μ’ λ₯κ° 30κ°μΈ μνλΌκ³ νλ€. κ²°λ‘ μ μΌλ‘ λ§μ§λ§μ μ‘°ν©μΌλ‘ νΈλ κ²μ λΆκ°λ₯νλ€λ κ²μΌλ‘ ν΄μν μ μλ€.
2οΈβ£ λ°©λ² (2) : Map μΌλ‘ μ’ λ₯λ³ κ°μ νμΈ ν μ‘°ν© μ¬μ© but μ‘°ν©μ μ§μ μ μΌλ‘ ꡬννμ§λ μμ
β‘οΈ μμ λ¬Έμ λ₯Ό ν΄κ²°νλ λ°©λ²μ μ¬μ€ μνμ μΈ λ¬Έμ λΌ μμΈν μ 리νμ§λ μμΌλ €κ³ νλ€. κ°λ μ μλμ κ°λ€.
β κ°λ
Point : μ‘°ν©μ μ¬μ©νμ§ μμμΌν¨
β‘οΈ (κ° μ· κ°μ + μμ λ κ²½μ°) λ₯Ό λ€ κ³±νκ³ λ§μ§λ§μ -1 (λͺ¨λ μμ λ κ²½μ°)
ex) λͺ¨μ 2κ° & μ κΈλΌμ€ 1κ° => (2+1) * (1*1) -1 = 5
μ κ°λ μ λ°λΌ κΈ°μ‘΄ μ½λμμ μ‘°ν© ν¨μλ₯Ό λΉΌκ³ λ¨μν μλ₯Ό κ³μ°νλλ‘ νμλ€.
①ꡬν μ½λ
import java.util.Map;
import java.util.Set;
import java.util.HashMap;
class Solution {
public int solution(String[][] clothes) {
int answer = 1;
// Map μμ±
Map<String, Integer> map = new HashMap<>();
// λ°°μ΄ λΆλ¦¬
for (String[] clothe : clothes) {
String type = clothe[1];
// map μ μ½μ
int count = 0;
if (map.containsKey(type)) {
count = map.get(type);
}
map.put(type, ++count);
}
// κ²½μ°μ μ νμΈ (1)
String[] types = map.keySet().toArray(new String[map.size()]);
int[] counts = new int[map.size()];
for (int i=0; i<types.length; i++) {
counts[i] = map.get(types[i]);
}
// κ²½μ°μ μ νμΈ (2)
for (int n : counts) {
answer *= n+1;
}
return --answer;
}
}
β’ κ²°κ³Ό

β‘οΈ 1λ² ν μ€νΈ μΌμ΄μ€λ μ ν΅κ³Όνμκ³ , μ 체μ μΌλ‘ μκ°λ μ€μ΄λ€μλ€. νμ§λ§ μλ£κ΅¬μ‘°λ₯Ό μ νμ©ν΄μλΌκΈ° 보λ€λ λ¨μ μνλ¬Έμ λΌ ν° μλ―Έλ μλ κ² κ°λ€.
3οΈβ£ λ°©λ² (3) : μ€ν°λ ν λ°©λ²(2) μ½λ κ°μ
β‘οΈ λ°©λ² (2) λ₯Ό νμ΄νλ©΄μ κ°μ νκ³ μΆμλ λΆλΆμ κ° μ’ λ₯λ³ κ°μλ₯Ό νμΈνκΈ° μν΄ λ°°μ΄μ μ μΈνκ³ key Set μμ νλμ© λΉΌμ€λ κ³Όμ μ΄μλ€. ν΄λΉ λΆλΆμ μ€ν°λλ₯Ό μ§ννλ©΄μ κ°μ μ μ νμΈν μ μμλ€. μΆκ°λ‘ μ΄λ°μ Map μμ μ€λ³΅ μ¬λΆλ₯Ό νμΈνκ³ κ°μ μ 보λ₯Ό λ€λ₯΄κ² νλ κ³Όμ μμλ κ°μ μ μ μ μ μμλ€.
β Map μ μ 보λ₯Ό λ£λ κ³Όμ : Map.getOrDefault() νμ©
리ν΄κ° : default V
λ©μλ : getOrDefault(Object key, V defaultValue)
β‘οΈ μ§μ λ ν€κ° λ§€νλ κ°μ λ°ννκ±°λ, λ§΅μ ν€μ λν λ§€νμ΄ μλ κ²½μ° defaultValue λ₯Ό λ°ν
// κΈ°μ‘΄ μ½λ
for (String[] clothe : clothes) {
String type = clothe[1];
// map μ μ½μ
int count = 0;
if (map.containsKey(type)) {
count = map.get(type);
}
map.put(type, ++count);
}
// κ°μ μ½λ
// λ°°μ΄ λΆλ¦¬
for (String[] clothe : clothes) {
String type = clothe[1];
map.put(type, map.getOrDefault(type, 0)+1);
}
β‘οΈ μ±λ₯λ©΄μμ μμ²λ κ°μ μ΄ μλ건 μλμ§λ§, 쑰건문λ μμ΄μ§κ³ μ 체μ μΈ μ½λ μλ μ€μκΈ° λλ¬Έμ κ°λ μ±μ΄ λμμ§ κ² κ°λ€.
β‘ μ’ λ₯λ³ κ°μλ₯Ό νμΈνλ κ³Όμ : ν₯μλ for λ¬Έ & Map.values() νμ©
// κΈ°μ‘΄ μ½λ
// key Set μ λ°°μ΄λ‘ λ³ν
String[] types = map.keySet().toArray(new String[map.size()]);
// vlaue κ°λ€μ λ΄κΈ° μν λ°°μ΄ μ μΈ
int[] counts = new int[map.size()];
// key λ°°μ΄ & value λ°°μ΄μ μννλ©° value κ° λ΄μ
for (int i=0; i<types.length; i++) {
counts[i] = map.get(types[i]);
// κ²½μ°μ μ νμΈ
for (int n : counts) {
answer *= n+1;
}
// κ°μ μ½λ
// λ°©λ² (1) : ν₯μλ for λ¬Έ νμ©
for (String type : map.keySet()) {
answer *= map.get(type) + 1;
}
// λ°©λ² (2) : Map.values() νμ©
for (int count : map.values()) {
answer *= count + 1;
}
β‘οΈ κ°λ μ±μ κΈ°λ³Έμ΄κ³ , λΆνμν μ μΈλ 2κ°λ μ€μλ€. λ©λͺ¨λ¦¬ μ°¨μ§μλ ν¨μ¨μ μΌ κ² κ°λ€.
π» νμ΄ μ½λ
import java.util.Map;
import java.util.Set;
import java.util.HashMap;
class Solution {
public int solution(String[][] clothes) {
int answer = 1;
// Map μμ±
Map<String, Integer> map = new HashMap<>();
// λ°°μ΄ λΆλ¦¬
for (String[] clothe : clothes) {
String type = clothe[1];
// map μ μ½μ
map.put(type, map.getOrDefault(type, 0)+1);
}
// κ²½μ°μ μ νμΈ
for (int count : map.values()) {
answer *= count + 1;
}
// μ무κ²λ μ
μ§ μμ κ²½μ° 1κ° λΉΌκΈ°
return --answer;
}
}
[level 2] Title: μμ₯, Time: 0.07 ms, Memory: 89.1 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@9df2d7f
Show file tree Showing 2 changed files with 227 additions and 0 deletions.
github.com