-
[Algo RhythmπΊπ] 2020 μΉ΄μΉ΄μ€ μΈν΄μ μμ μ΅λνAlgo RhythmπΊπ/others 2020. 7. 5. 23:40
λ¬Έμ μ€λͺ
IT λ²€μ² νμ¬λ₯Ό μ΄μνκ³ μλ λΌμ΄μΈμ 맀λ μ¬λ΄ ν΄μ»€ν€ λνλ₯Ό κ°μ΅νμ¬ μ°μΉμμκ² μκΈμ μ§κΈνκ³ μμ΅λλ€.
μ΄λ² λνμμλ μ°μΉμμκ² μ§κΈλλ μκΈμ μ΄μ λνμλ λ€λ₯΄κ² λ€μκ³Ό κ°μ λ°©μμΌλ‘ κ²°μ νλ €κ³ ν©λλ€.
ν΄μ»€ν€ λνμ μ°Έκ°νλ λͺ¨λ μ°Έκ°μλ€μκ²λ μ«μλ€κ³Ό 3κ°μ§μ μ°μ°λ¬Έμ(+, -, *) λ§μΌλ‘ μ΄λ£¨μ΄μ§ μ°μ° μμμ΄ μ λ¬λλ©°, μ°Έκ°μμ λ―Έμ μ μ λ¬λ°μ μμμ ν¬ν¨λ μ°μ°μμ μ°μ μμλ₯Ό μμ λ‘κ² μ¬μ μνμ¬ λ§λ€ μ μλ κ°μ₯ ν° μ«μλ₯Ό μ μΆνλ κ²μ λλ€.
λ¨, μ°μ°μμ μ°μ μμλ₯Ό μλ‘ μ μν λ, κ°μ μμμ μ°μ°μλ μμ΄μΌ ν©λλ€. μ¦, + > - > * λλ - > * > + λ±κ³Ό κ°μ΄ μ°μ°μ μ°μ μμλ₯Ό μ μν μ μμΌλ +,* > - λλ * > +,-μ²λΌ 2κ° μ΄μμ μ°μ°μκ° λμΌν μμλ₯Ό κ°μ§λλ‘ μ°μ°μ μ°μ μμλ₯Ό μ μν μλ μμ΅λλ€. μμμ ν¬ν¨λ μ°μ°μκ° 2κ°λΌλ©΄ μ μν μ μλ μ°μ°μ μ°μ μμ μ‘°ν©μ 2! = 2κ°μ§μ΄λ©°, μ°μ°μκ° 3κ°λΌλ©΄ 3! = 6κ°μ§ μ‘°ν©μ΄ κ°λ₯ν©λλ€.
λ§μ½ κ³μ°λ κ²°κ³Όκ° μμλΌλ©΄ ν΄λΉ μ«μμ μ λκ°μΌλ‘ λ³ννμ¬ μ μΆνλ©° μ μΆν μ«μκ° κ°μ₯ ν° μ°Έκ°μλ₯Ό μ°μΉμλ‘ μ μ νλ©°, μ°μΉμκ° μ μΆν μ«μλ₯Ό μ°μΉμκΈμΌλ‘ μ§κΈνκ² λ©λλ€.
μλ₯Ό λ€μ΄, μ°Έκ°μ μ€ λ€μ€κ° μλμ κ°μ μμμ μ λ¬λ°μλ€κ³ κ°μ ν©λλ€.
"100-200*300-500+20"
μΌλ°μ μΌλ‘ μν λ° μ μ°νμμ μ½μλ μ°μ°μ μ°μ μμμ λ°λ₯΄λ©΄ λνκΈ°μ λΉΌκΈ°λ μλ‘ λλ±νλ©° κ³±νκΈ°λ λνκΈ°, λΉΌκΈ°μ λΉν΄ μ°μ μμκ° λμ * > +,- λ‘ μ°μ μμκ° μ μλμ΄ μμ΅λλ€.
λν κ·μΉμ λ°λΌ + > - > * λλ - > * > + λ±κ³Ό κ°μ΄ μ°μ°μ μ°μ μμλ₯Ό μ μν μ μμΌλ +,* > - λλ * > +,- μ²λΌ 2κ° μ΄μμ μ°μ°μκ° λμΌν μμλ₯Ό κ°μ§λλ‘ μ°μ°μ μ°μ μμλ₯Ό μ μν μλ μμ΅λλ€.
μμμ μ°μ°μκ° 3κ° μ£Όμ΄μ‘μΌλ―λ‘ κ°λ₯ν μ°μ°μ μ°μ μμ μ‘°ν©μ 3! = 6κ°μ§μ΄λ©°, κ·Έ μ€ + > - > * λ‘ μ°μ°μ μ°μ μμλ₯Ό μ νλ€λ©΄ κ²°κ΄κ°μ 22,000μμ΄ λ©λλ€.
λ°λ©΄μ * > + > - λ‘ μ°μ°μ μ°μ μμλ₯Ό μ νλ€λ©΄ μμμ κ²°κ΄κ°μ -60,420 μ΄μ§λ§, κ·μΉμ λ°λΌ μ°μΉ μ μκΈμ μ λκ°μΈ 60,420μμ΄ λ©λλ€.
μ°Έκ°μμκ² μ£Όμ΄μ§ μ°μ° μμμ΄ λ΄κΈ΄ λ¬Έμμ΄ expressionμ΄ λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ°μΉ μ λ°μ μ μλ κ°μ₯ ν° μκΈ κΈμ‘μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
[μ νμ¬ν]
-
expressionμ κΈΈμ΄κ° 3 μ΄μ 100 μ΄νμΈ λ¬Έμμ΄μ λλ€.
-
expressionμ 곡백문μ, κ΄νΈλ¬Έμ μμ΄ μ€λ‘μ§ μ«μμ 3κ°μ§μ μ°μ°μ(+, -, *) λ§μΌλ‘ μ΄λ£¨μ΄μ§ μ¬λ°λ₯Έ μ€μνκΈ°λ²(μ°μ°μ λ λμ μ¬μ΄μ μ°μ°κΈ°νΈλ₯Ό μ¬μ©νλ λ°©μ)μΌλ‘ ννλ μ°μ°μμ λλ€. μλͺ»λ μ°μ°μμ μ λ ₯μΌλ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
-
μ¦, "402+-561*"μ²λΌ μλͺ»λ μμμ μ¬λ°λ₯Έ μ€μνκΈ°λ²μ΄ μλλ―λ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
-
-
expressionμ νΌμ°μ°μ(operand)λ 0 μ΄μ 999 μ΄νμ μ«μμ λλ€.
-
μ¦, "100-2145*458+12"μ²λΌ 999λ₯Ό μ΄κ³Όνλ νΌμ°μ°μκ° ν¬ν¨λ μμμ μ λ ₯μΌλ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
-
"-56+100"μ²λΌ νΌμ°μ°μκ° μμμΈ μμλ μ λ ₯μΌλ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
-
expressionμ μ μ΄λ 1κ° μ΄μμ μ°μ°μλ₯Ό ν¬ν¨νκ³ μμ΅λλ€.
-
μ°μ°μ μ°μ μμλ₯Ό μ΄λ»κ² μ μ©νλλΌλ, expressionμ μ€κ° κ³μ°κ°κ³Ό μ΅μ’ κ²°κ΄κ°μ μ λκ°μ΄ 263 - 1 μ΄νκ° λλλ‘ μ λ ₯μ΄ μ£Όμ΄μ§λλ€.
-
κ°μ μ°μ°μλΌλ¦¬λ μμ μλ κ²μ μ°μ μμκ° λ λμ΅λλ€.
μ΄λ»κ² νμλ
import java.util.ArrayList; import java.lang.StringBuilder; import java.util.Arrays; import java.util.stream.Collectors; class Solution { public long solution(String expression) { long maxPrizeMoney = Long.MIN_VALUE; ArrayList<String> tokens = tokenize(expression); ArrayList<String> optrs = extractOptr(expression); // get permuations of operators ArrayList<ArrayList<String>> permOfOptrs = new ArrayList<ArrayList<String>>(); permutate(permOfOptrs, optrs.toArray(new String[0]), 0, optrs.size()); // get maximum of prize money for(ArrayList<String> priorityOfOptrs : permOfOptrs) { ArrayList<String> copyOfTokens = new ArrayList<>(tokens); long prizeMoney = 0; // reduce for(String pOptr : priorityOfOptrs) { while(copyOfTokens.indexOf(pOptr) != -1) { int idx = copyOfTokens.indexOf(pOptr); long result = 0; long opd1 = Long.parseLong(copyOfTokens.get(idx - 1)); long opd2 = Long.parseLong(copyOfTokens.get(idx + 1)); switch(pOptr) { case "+": result = opd1 + opd2; break; case "*": result = opd1 * opd2; break; case "-": result = opd1 - opd2; break; } for(int a = 0; a < 3; a++) copyOfTokens.remove(idx - 1); copyOfTokens.add(idx - 1, String.valueOf(result)); } } prizeMoney = Math.abs(Long.parseLong(copyOfTokens.get(0))); // renew the maximum of prize money maxPrizeMoney = (maxPrizeMoney >= prizeMoney) ? maxPrizeMoney : prizeMoney; } return maxPrizeMoney; } public void permutate(ArrayList<ArrayList<String>> permOfOptrs, String[] optrs, int depth, int n) { if(depth == n) { ArrayList<String> list = Arrays.stream(optrs).collect(Collectors.toCollection(ArrayList::new)); permOfOptrs.add(list); return; } for(int i = depth; i < n; i++) { swap(optrs, depth, i); permutate(permOfOptrs, optrs, depth + 1, n); swap(optrs, depth, i); } } public void swap(String[] arr, int depth, int i) { String temp = arr[depth]; arr[depth] = arr[i]; arr[i] = temp; } public ArrayList<String> extractOptr(String exp) { ArrayList<String> optrs = new ArrayList<>(); if(exp.contains("-")) optrs.add("-"); if(exp.contains("+")) optrs.add("+"); if(exp.contains("*")) optrs.add("*"); return optrs; } public ArrayList<String> tokenize(String exp) { ArrayList<String> tokens = new ArrayList<>(); char[] expArr = exp.toCharArray(); StringBuilder sbd = new StringBuilder(); for(int i = 0; i < expArr.length; i++) { if(expArr[i] == '-' || expArr[i] == '+' || expArr[i] == '*') { tokens.add(sbd.toString()); sbd.setLength(0); // clear sbd.append(expArr[i]); tokens.add(sbd.toString()); sbd.setLength(0); // clear } else { sbd.append(expArr[i]); } if(i == expArr.length - 1) tokens.add(sbd.toString()); // add last number } return tokens; } }
μ μ λ κ² νμλ
λ¨Όμ μ£Όμ΄μ§ μμμ tokenizeνλ€.
κ·Έλ¦¬κ³ λμ μμμ μλ μ°μ°μλ€μ νμ ν λ€ κ·Έκ²λ€μ μμ΄μ ꡬνλ€.
μμ΄λ€μ μ§ν©μμ μμ΄ μ¦, μ°μ°μμ μ°μ μμλ₯Ό νλμ© κ°μ Έμ¨λ€.
κ·Έλ¦¬κ³ λμ μμμ tokenizeν listμμ κ·Έ μ°μ°μλ₯Ό κ°μ§κ³ μλ indexλ₯Ό μ°Ύλλ€.
λ§μ½ -1μ΄ returnλμμΌλ©΄ μλ€λ λ»μ΄κΈ° λλ¬Έμ λ°λ³΅λ¬Έμμ νμΆνλ€.
λ§μ½ κ·Έ μ°μ°μκ° μ‘΄μ¬νλ©΄ μ°μ°μμ λ§λ μ°μ°μ ν λ€ resultλΌλ λ³μμ μ μ₯νλ€.
κ·Έλ¦¬κ³ κ·Έ μ°μ°μμ μΌμͺ½, μ€λ₯Έμͺ½μ μλ νΌμ°μ°μ λ κ°λ₯Ό μμ νλ€.
λ€μμΌλ‘ μΌμͺ½ μ°μ°μκ° μλ indexμ resultλ₯Ό stringμΌλ‘ λ³ννμ¬ addνλ€.
μ κ³Όμ μ μμ΄μ μλ λͺ¨λ μ°μ°μμ λν΄ λ°λ³΅νλ©΄ κ²°κ³Ό μ¦, μ°μΉμκΈμ΄ λμ¨λ€.
μ°μΉμκΈμ longμΌλ‘ parseν λ€ κ°μ₯ λ§μ μ°μΉμκΈμΈμ§ νμΈνλ€.
μ κ³Όμ μ μμ΄λ€μ μ§ν©μμ λͺ¨λ μμ΄μ νμΈν λκΉμ§ λ°λ³΅νλ€.
무μμ λ°°μ λ
μλ λΈλ‘κ·Έλ₯Ό μ°Έκ³ ν΄μ μμ΄ κ΅¬νλ μκ³ λ¦¬μ¦μ ꡬννλ€.
https://bcp0109.tistory.com/14
λ¬Έμ λ₯Ό μ½κ³ λμ νμ°Έ κ³ λ―Όνλ€κ° μ΄ μκ³ λ¦¬μ¦μ μκ°νλ€. νμ§λ§ λ무 brute forceλ°©μμ΄κΈ° λλ¬Έμ μ΄κ±΄ μ€ν¨ν κ²μ΄λΌκ³ μκ°νλ€.
νμ§λ§ μ΄κ² μ κ±Έ…! 3μ€ λ°λ³΅λ¬Έμ ν΅κ³ΌμμΌμ€λ€…!π π
λΆλͺ μΉ΄μΉ΄μ€μμ μλν ν¨μ¨μ μΈ μ½λκ° μμ κ² κ°μλ°... ν ... μμ§ λ΄ λ¨Έλ¦¬λ‘λ μ λͺ¨λ₯΄κ² λ€...
'Algo RhythmπΊπ > others' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
-