문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/67257
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 핵심
- 대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다. - 참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.
알고리즘
1.문자열 기호가 몇가지인지 분류
2.가지수에 따른 완전 탐색진행
코드
public static long solution(String expression) {
long answer = 0;
List<String> tokens = new ArrayList<>();
Set<String> operators = new LinkedHashSet<>();
StringBuilder num = new StringBuilder();
for (char c : expression.toCharArray()) {
if (Character.isDigit(c)) {
num.append(c);
} else {
tokens.add(num.toString());
tokens.add(String.valueOf(c));
operators.add(String.valueOf(c));
num.setLength(0);
}
}
tokens.add(num.toString());
System.out.println("tokens: " + tokens + " | operators: " + operators);
if (operators.size() == 1) {
System.out.println("수식이1개임");
answer = Long.parseLong(tokens.get(0));
for (int i = 1; i < tokens.size(); i += 2) {
long tnum = Long.parseLong(tokens.get(i + 1));
switch (tokens.get(i)) {
case "+":
answer += tnum;
break;
case "-":
answer -= tnum;
break;
case "*":
answer *= tnum;
break;
}
}
answer = Math.abs(answer);
System.out.println(answer);
return answer;
} else if (operators.size() == 2) {
System.out.println("수식이2개임");
List<String> opList = new ArrayList<>(operators);
for (int p = 0; p < 2; p++) {
List<String> temp = new ArrayList<>(tokens);
for (int o = 0; o < 2; o++) {
String op = opList.get((p + o) % 2);
for (int i = 1; i < temp.size(); i += 2) {
if (temp.get(i).equals(op)) {
long a = Long.parseLong(temp.get(i - 1));
long b = Long.parseLong(temp.get(i + 1));
long result = 0;
switch (op) {
case "+":
result = a + b;
break;
case "-":
result = a - b;
break;
case "*":
result = a * b;
break;
}
temp.set(i - 1, String.valueOf(result));
temp.remove(i);
temp.remove(i);
i -= 2;
}
}
}
answer = Math.max(answer, Math.abs(Long.parseLong(temp.get(0))));
}
System.out.println(answer);
return answer;
} else if (operators.size() == 3) {
System.out.println("수식이3개임");
List<String> opList = new ArrayList<>(operators);
int[][] orders = {
{ 0, 1, 2 },
{ 0, 2, 1 },
{ 1, 0, 2 },
{ 1, 2, 0 },
{ 2, 0, 1 },
{ 2, 1, 0 }
};
for (int[] order : orders) {
List<String> temp = new ArrayList<>(tokens);
for (int o : order) {
String op = opList.get(o);
for (int i = 1; i < temp.size(); i += 2) {
if (temp.get(i).equals(op)) {
long a = Long.parseLong(temp.get(i - 1));
long b = Long.parseLong(temp.get(i + 1));
long result = 0;
switch (op) {
case "+":
result = a + b;
break;
case "-":
result = a - b;
break;
case "*":
result = a * b;
break;
}
temp.set(i - 1, String.valueOf(result));
temp.remove(i);
temp.remove(i);
i -= 2;
}
}
}
answer = Math.max(answer, Math.abs(Long.parseLong(temp.get(0))));
}
System.out.println(answer);
return answer;
}
return answer;
}
결과
gpt피드백
1. 알고리즘 평가
결론부터 말하면, 알고리즘 선택은 정확해. 특히 연산자 종류가 최대 3개라는 제한을 이용해 6가지 우선순위를 직접 나열한 건 합리적인 접근이야.
개선점 ① 연산자 개수에 따른 분기 통합
개선점 ② 시간복잡도
2. 코드 평가
개선점 ① 중복된 연산 로직 제거
가장 큰 개선점이야.
현재 2개 연산자 분기와 3개 연산자 분기에서 사실상 동일한 계산 코드가 반복되고 있어.
개선점 ② 하드코딩 순열 유지하면서 중복 제거
DFS가 부담스럽다면 지금의 하드코딩 방식도 유지할 수 있어.
연산자가 1개, 2개, 3개인 경우를 각각 분기하지 말고 순열 배열만 다르게 설정하면 돼.
후기
경우의 수가 명확히 정해진 문제여서
하드코딩 했다 그마저도 귀찮아서
알고리즘만 짜고 코드는 gpt한테 써달라고 했다 ㅋㅋ
'코테 > lvl2' 카테고리의 다른 글
| 프로그래머스 점프와 순간 이동(lvl2) 풀어보기 (0) | 2026.10.16 |
|---|---|
| 프로그래머스 스킬트리(lvl2) 풀어보기 (0) | 2026.10.16 |
| 프로그래머스 삼각 달팽이(lvl2) 풀어보기 (0) | 2026.10.12 |
| 프로그래머스 [3차] n진수 게임(lvl2) 풀어보기 (0) | 2026.10.08 |
| 프로그래머스 쿼드압축 후 개수 세기(lvl2) 풀어보기 (0) | 2026.10.08 |