728x90
이해하기
처음 들었던 생각은 완전 탐색을 해야겠으니 dfs를 써야겠다. 이거 전에 풀었던 피로도 문제랑 비슷하게 풀면 되겠네~ 였다. (그리고 풀이 실패)
이번에 참고한 블로그는 아래!
이 분의 풀이는 다음과 같다.
- 연산자 순서를 전부 배열로 만들어둔다.
- 문자열에서 숫자와 연산자를 분리하여 ArrayList에 추가
- 연산자를 만나면, 앞은 숫자이므로 먼저 추가
- 연산자 추가
- 1, 2번만 for문에서 수행하므로 마지막 숫자까지 추가!
- 미리 만들어둔 연산자 우선순위 6개 경우에 대해 계산한다.
- list에서 op[i][k]에 해당하는 수식을 만나면 자신의 앞의 숫자와 뒤의 숫자를 계산해준 후, 계산한 숫자로 앞의 숫자를 바꾼다. (자신과 다음 위치 숫자 제거)
- 수식 계산이 끝나면 max 값 비교
import java.util.*;
class Solution {
static long answer = Long.MIN_VALUE;
static String[][] op = {{"+", "-", "*"}, {"+", "*", "-"}, {"*", "+", "-"}, {"*", "-", "+"}, {"-", "*", "+"}, {"-", "+", "*"}};
public long solution(String expression) {
ArrayList<String> list = new ArrayList<>();
int start = 0;
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') {
list.add(expression.substring(start, i));
list.add(expression.charAt(i) + "");
start = i + 1;
}
}
list.add(expression.substring(start));
for (int i = 0; i < op.length; i++) {
ArrayList<String> subList = new ArrayList<>(list);
for (int j = 0; j < 3; j++) {
for (int k = 0; k < subList.size(); k++) {
if (op[i][j].equals(subList.get(k))) {
subList.set(k - 1, calc(subList.get(k - 1), subList.get(k), subList.get(k + 1)));
subList.remove(k);
subList.remove(k);
k--;
}
}
}
answer = Math.max(answer, Math.abs(Long.parseLong(subList.get(0))));
}
return answer;
}
public String calc(String num1, String op, String num2) {
long n1 = Long.parseLong(num1);
long n2 = Long.parseLong(num2);
if (op.equals("+")) {
return n1 + n2 + "";
} else if (op.equals("-")) {
return n1 - n2 + "";
} else {
return n1 * n2 + "";
}
}
}
이 풀이를 보고 약간 당황했다.
아니 완탐은 완탐인데, dfs...? bfs? 이게 뭐지?? 라는 생각이 들었다.
다른 분들의 풀이도 많이 살펴보았지만 대부분 이런 방식으로 푸셨다.
요 풀이를 좀 더 응용해서 순열로 뽑아내는 걸 해보겠다.
문제풀이
static long answer = Long.MIN_VALUE;
static List<char[]> opList = new ArrayList<>();
public long solution(String expression) {
ArrayList<String> list = new ArrayList<>();
int start = 0;
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') {
list.add(expression.substring(start, i));
list.add(expression.charAt(i) + "");
start = i + 1;
}
}
list.add(expression.substring(start));
char[] op = {'+', '-', '*'};
perm(op, 0);
for (int i = 0; i < opList.size(); i++) {
ArrayList<String> subList = new ArrayList<>(list);
char[] curOp = opList.get(i);
for (int j = 0; j < curOp.length; j++) {
for (int k = 0; k < subList.size(); k++) {
if ((curOp[j] + "").equals(subList.get(k))) {
subList.set(k - 1, calc(subList.get(k - 1), subList.get(k), subList.get(k + 1)));
subList.remove(k);
subList.remove(k);
k--;
}
}
}
answer = Math.max(answer, Math.abs(Long.parseLong(subList.get(0))));
}
return answer;
}
public String calc(String num1, String op, String num2) {
long n1 = Long.parseLong(num1);
long n2 = Long.parseLong(num2);
if (op.equals("+")) {
return n1 + n2 + "";
} else if (op.equals("-")) {
return n1 - n2 + "";
} else {
return n1 * n2 + "";
}
}
public void perm(char[] op, int depth) {
if (depth == op.length) {
char[] temp = op.clone();
opList.add(temp);
return;
}
for (int i = depth; i < op.length; i++) {
swap(op, depth, i);
perm(op, depth + 1);
swap(op, depth, i);
}
}
public void swap(char[] op, int depth, int i) {
char temp = op[depth];
op[depth] = op[i];
op[i] = temp;
}
시간은 전의 풀이보다 오래 걸리지만 연산자 개수가 바뀌는 경우를 위해서는 이렇게 푸는게 더 나을지도...
하여튼 힘들닷...^^
'JAVA > Coding Test Study' 카테고리의 다른 글
[Lv.2] 카펫 : Java (0) | 2024.04.01 |
---|---|
[Lv.3] 여행경로 : Java (0) | 2024.03.27 |
[Lv.3] 단어 변환 : Java (0) | 2024.03.27 |
[Lv.3] 네트워크 : Java (0) | 2024.03.26 |
[Lv.2] 타겟 넘버 : Java (0) | 2024.03.26 |