문제 간단 해석
주어진 수식에 사칙연산 우선순위를 정해줬을 때 최댓값이 나오도록 하는 문제. 효율까지 챙기려면 의외로 까다롭다.
Java
풀이 코드
import java.util.Map;
import java.util.HashMap;
import java.util.Deque;
import java.util.ArrayDeque;
class Solution {
private Map<String, Boolean> map = new HashMap<>();
private Deque<String> stack = new ArrayDeque<>();
public String cal(String s1, String o, String s2) {
long l1 = Long.parseLong(s1);
long l2 = Long.parseLong(s2);
long answer = 0;
switch (o) {
case "+":
answer = l1 + l2;
break;
case "-":
answer = l1 - l2;
break;
case "*":
answer = l1 * l2;
break;
default:
break;
}
return Long.toString(answer);
}
public long express(String[] s, int step) {
if (step == 3)
return Math.abs(Long.parseLong(s[0]));
long now = 0;
for (String o: map.keySet()) {
if (!map.get(o))
continue;
map.put(o, false);
stack.clear();
for (int i = 0; i < s.length; i++) {
if (o.equals(s[i]))
stack.addLast(cal(stack.removeLast(), s[i], s[++i]));
else
stack.addLast(s[i]);
}
now = Math.max(now, express(stack.toArray(new String[stack.size()]), step + 1));
map.put(o, true);
}
return now;
}
public long solution(String expression) {
map.put("+", true);
map.put("-", true);
map.put("*", true);
StringBuilder sb = new StringBuilder();
String c;
for (int i = 0; i < expression.length(); i++) {
c = Character.toString(expression.charAt(i));
if (!map.containsKey(c)){
sb.append(c);
} else {
stack.addLast(sb.toString());
stack.addLast(c);
sb.setLength(0);
}
}
stack.addLast(sb.toString());
return express(stack.toArray(new String[stack.size()]), 0);
}
}해석
Deque<String> stack = new ArrayDeque<>();stack을 ArrayDeque로 선언했다. 기존 Stack 자료형은 현 시점에서 문제가 있다고 여겨진다. 자세한 건 여기에서 확인.
map.put("+", true);
map.put("-", true);
map.put("*", true);map에 사용될 사칙연산과, DFS를 돌릴 때 사용 가능한지 아닌지를 체크할 true를 넣어줬다.
for (int i = 0; i < expression.length(); i++) {
c = Character.toString(expression.charAt(i));
if (!map.containsKey(c)){
sb.append(c);
} else {
stack.addLast(sb.toString());
stack.addLast(c);
sb.setLength(0);
}
}
stack.addLast(sb.toString());
return express(stack.toArray(new String[stack.size()]), 0);한 글자씩 가져와서 stack에 담을지 말지 결정한다. stack을 String 자료형으로 선언했기에 expression에서 charAt으로 char를 가져와 String으로 변환하여 사용하기로 했다.
만약 가져온 글자가 +, -, *가 아니라면 sb에 추가한다.
+, -, *라면 계속 담아주었던 sb의 글자들을 한 번에 stack에 담고, 이번에 가져온 사칙연산 기호도 마찬가지로 담는다.
(stack 내에는 숫자와 사칙연산이 나눠져 들어가게 되므로 앞으로의 계산이 굉장히 쉬워진다.)
그 후 sb를 초기화한다.
반복이 끝나면 sb에 남아있던 숫자를 stack에 담는다.
그 후 express 함수에 stack을 array로 바꿔 넣는다.
stack 그대로 넣어도 되겠지만, express에서 계속 clone을 해줘야 하기에.. 효율이 좋지 않을 것 같아 변환하여 넣었다.
public long express(String[] s, int step) {
if (step == 3)
return Math.abs(Long.parseLong(s[0]));
long now = 0;
for (String o: map.keySet()) {
if (!map.get(o))
continue;
map.put(o, false);
stack.clear();
for (int i = 0; i < s.length; i++) {
if (o.equals(s[i]))
stack.addLast(cal(stack.removeLast(), s[i], s[++i]));
else
stack.addLast(s[i]);
}
now = Math.max(now, express(stack.toArray(new String[stack.size()]), step + 1));
map.put(o, true);
}
return now;
}만약 모든 사칙연산을 수행했다면 남은 결과를 long 변환 후 절댓값 반환.
어떤 사칙연산을 수행할 지 for문을 통해 가져온다.
만약 이미 선택한 사칙연산이라면 건너뛴다.
해당 사칙연산 값을 false로 변경한 후, stack을 비운다. 조금 전에 Array로 복사하여 건네줬으니 할 일은 다 한 셈. 비우고 다시금 재활용하도록 한다.
얻어온 글자가 이번에 지정한 사칙연산 기호가 아니라면 stack에 값을 넣어준다.
만약 지정한 사칙연산 기호라면, 방금 넣어둔 stack에서 최신값을 빼오고(숫자), 해당 사칙연산 기호와 그 이후에 있는 숫자를 cal 함수에 넣어 계산결과를 가져온 후 stack에 넣는다.
작업이 모두 끝났으면 재귀를 통해 다시 반복시킨다. 그렇게 얻어온 최종값 중 가장 큰 값을 지니고 있게끔 한다.
해당 for문이 종료되기 전에, 이번에 지정한 사칙연산 값을 다시 true로 반환하여 다음 재귀에서 사용할 수 있도록 한다.
그 후 최종값 반환.
public String cal(String s1, String o, String s2) {
long l1 = Long.parseLong(s1);
long l2 = Long.parseLong(s2);
long answer = 0;
switch (o) {
case "+":
answer = l1 + l2;
break;
case "-":
answer = l1 - l2;
break;
case "*":
answer = l1 * l2;
break;
default:
break;
}
return Long.toString(answer);
}cal 함수는 특별한 게 없으므로 생략.
Python
풀이 코드
from itertools import permutations
def solution(expression):
operator = {
'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y
}
exp = []
start = 0
for i in range(1, len(expression)):
if expression[i] in operator:
exp.append(int(expression[start:i]))
exp.append(expression[i])
start = i + 1
exp.append(int(expression[start:]))
total = 0
for oper in permutations(operator):
ex = exp[:]
for op in oper:
idx = 1
while idx < len(ex):
if ex[idx] == op:
ex[idx] = operator[op](ex[idx - 1], ex[idx + 1])
del(ex[idx + 1])
del(ex[idx - 1])
idx = 0
idx += 1
val = ex[0]
val = -val if val < 0 else val
total = max(total, val)
return total해석
for i in range(1, len(expression)):
if expression[i] in operator:
exp.append(int(expression[start:i]))
exp.append(expression[i])
start = i + 1
exp.append(int(expression[start:]))(첫번째 글자는 무조건 숫자이므로) 두번째 글자부터 가져와 기호인지 확인.
기호라면 숫자로 변환하여 exp에 넣는다.
기호도 같이 넣고 start 범위 재정의.
반복문 끝난 후 남은 숫자도 마저 넣어준다.
for oper in permutations(operator):
ex = exp[:]
for op in oper:
idx = 1
while idx < len(ex):
if ex[idx] == op:
ex[idx] = operator[op](ex[idx - 1], ex[idx + 1])
del(ex[idx + 1])
del(ex[idx - 1])
idx = 0
idx += 1
val = ex[0]
val = -val if val < 0 else val
total = max(total, val)
return total순열을 생성, oper에서 하나씩 정의.
exp 복사해서 ex에 넣어준다.
정의된 순열에서 하나씩 가져와 op에 정의.
ex에서 op와 같은 기호가 있다면, 해당 기호에 대해 연산한 후 그 결과를 기호 자리에 넣는다.
기호 자리의 뒤, 앞 값들을 삭제.
다시 처음부터 살핀다.
해당 순열에서의 반복이 끝나면 값을 가져와 total이 최댓값을 가지게끔 한다.
그 후 total 반환.
operator = {
'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y
}operator는 람다를 이용하여 해당하는 기호에 맞는 연산을 수행.
여담
Java로 풀자니 꽤나 오래 걸린 문제. 많이 익숙해져야 할 것 같다.
Python 풀이는.. 별로 좋은 코드가 아니다.
리스트 내 값을 삭제해버리면, 그 뒤에 있는 값들을 앞으로 끌고와 재정의해야 하기에 Java 풀이처럼 stack을 활용하는 게 더 나을 듯.
