코딩 테스트/프로그래머스
[프로그래머스][Level2][JAVA] 수식 최대화
갓생사는 김초원의 개발 블로그
2020. 10. 24. 01:16
[문제 설명]
https://programmers.co.kr/learn/courses/30/lessons/67257
코딩테스트 연습 - 수식 최대화
IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과
programmers.co.kr
[풀이 과정]
문제를 해결하는데에 3가지 알고리즘 및 자료구조 지식을 이용했다.
1. 순열
2. 수식의 계산 - 중위표기법, 후위표기법
3. 스택
(2를 계산할 때 3이 사용된다.)
1. 순열
문제에서는 +, -, * 이 세가지 연산자의 우선순위를 자유롭게 재정의 하여 가장 큰 답을 만드는 계산식의 결과를 리턴하라고 한다.
+, -, * 의 우선순위를 모두 만들어봐야 어떤 우선순위가 가장 큰 답을 만드는지 알 수 있다.
아이템의 중복을 허용하지 않으며 순서를 고려하는 나열법이므로 순열을 이용하여 경우의 수를 모두 구할 수 있다.
public static void permutation(int[] items, int[] buckets, int k) {
if (k == 0) {
// 경우의 수로 하고자 하는 로직을 실행
return;
}
int lastIndex = buckets.length - k - 1;
for (int i = 0; i < items.length; i++) {
boolean flag = true;
for (int j = 0; j <= lastIndex; j++) {
if (buckets[j] == items[i]) {
flag = false;
}
}
if (flag) {
buckets[lastIndex + 1] = items[i];
permutation(items, buckets, k - 1);
}
}
}
2. 수식의 계산 - 중위표기법, 후위표기법
3. 스택
후위표기법의 특징은 수식에 괄호가 없어도 우선순위가 반영되어 있다.
즉, 문제에 나온 중위표기법을 적용하고 자는 우선순위가 반영된 후위표기법으로 만들 수 있다.
적용하고자 하는 우선순위는 순열에서 구한 경우의 수들이다. 각 경우에 수에 대응하는 후위표기법을 만든다.
중위표기법 및 후위표기법 계산에는 자료구조 스택을 사용한다.
/**
* 중위 표기법 -> 후위 표기법으로 변환
* @param postfix
* @param priorities
* @return
*/
public static String[] postfixToInfix(String postfix, int[] priorities) {
// String을 배열로 변환
String[] postfixArray = strToArray(postfix);
String[] infixArray = new String[postfixArray.length];
String[] op = {"+", "-", "*"};
Stack<String> stack = new Stack<>();
int index = 0;
for (int i = 0; i < postfixArray.length; i++) {
// 배열의 원소가 연산자이면
if (Arrays.asList(op).contains(postfixArray[i])) {
// 스택이 비어있으면
if (stack.isEmpty()) {
// 연산자를 push
stack.push(postfixArray[i]);
} else {
// 스택이 비어있지 않다면
// 스택에 먼저 들어있는 연산자들이 현재 연산자보다 우선순위가 높다면 pop
while (!stack.isEmpty() && compareToOperation(postfixArray[i], stack.peek(), priorities)) {
// 후위표기법 계산식에 스택에서 pop한 연산자 출력
infixArray[index++] = stack.pop();
}
// 현재 연산자를 스택에 push
stack.push(postfixArray[i]);
}
// 피연산자이면 후위표기법 계산식에 바로 출력
} else {
infixArray[index++] = postfixArray[i];
}
}
// 스택에 남아있던 연산자들 모두 후위표기법 계산식에 pop하여 출력
while (!stack.isEmpty()) {
infixArray[index++] = stack.pop();
}
return infixArray;
}
public static String[] strToArray(String postfix) {
String[] numStrArray = postfix.replaceAll("[^0-9]", " ").split(" ");
String[] opStrArray = postfix.replaceAll("[^[+]-[*]]", "").split("");
String[] result = new String[numStrArray.length + opStrArray.length];
int index = 0;
for (int i = 0; i < numStrArray.length; i++) {
result[index++] = numStrArray[i];
if (i != numStrArray.length - 1) {
result[index++] = opStrArray[i];
}
}
return result;
}
/**
* 연산자 우선순위 체크 로직
* @param op1
* @param op2
* @param priorities
* @return
*/
public static boolean compareToOperation(String op1, String op2, int[] priorities) {
String[] op = {"+", "-", "*"};
if (op1.equals(op[priorities[0]])) {
if (op2.equals(op[priorities[0]])) {
return true;
}
}
if (op1.equals(op[priorities[1]])) {
if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]])) {
return true;
}
}
if (op1.equals(op[priorities[2]])) {
if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]]) || op2.equals(op[priorities[2]])) {
return true;
}
}
return false;
}
중위표기법을 후위표기법으로 변환하였으면 후위표기법을 계산해야 한다.
우선순위 경우의 수들에 대응한 후위표기법들의 결과값을 비교하여 가장 큰 값이 이 문제의 답이다.
/**
* 후위 표기법 계산 메서드
* @param infix
* @return
*/
public static long getInfixResult(String[] infix) {
long answer = 0;
String[] op = {"+", "-", "*"};
Stack<String> stack = new Stack<>();
for (int i = 0; i < infix.length; i++) {
// 후위표기법의 현재 원소가 '연산자'인 경우
if (Arrays.asList(op).contains(infix[i])) {
String operation = infix[i];
// 스택에서 피연산자들 2개를 pop
long second = Long.parseLong(stack.pop());
long first = Long.parseLong(stack.pop());
// 현재 원소의 종류에 따라 피연산자들을 계산한 결과값을 스택에 push
switch (operation) {
case "+":
stack.push(String.valueOf(first + second));
break;
case "-":
stack.push(String.valueOf(first - second));
break;
case "*":
stack.push(String.valueOf(first * second));
break;
case "/":
stack.push(String.valueOf(first / second));
break;
}
// 현재 원소가 피연산자이면 스택에 push
} else {
stack.push(infix[i]);
}
}
answer = Math.abs(Long.parseLong(stack.pop()));
return answer;
}
[JAVA code]
package com.algorithm.level2;
import java.util.Arrays;
import java.util.Stack;
public class Test22 {
public static long answer = 0;
public static String postfix = "";
public static void main(String[] args) {
String expression = "50*6-3*2";
System.out.println("answer : " + solution(expression));
}
public static long solution(String expression) {
answer = 0;
postfix = expression;
int[] items = {0, 1, 2};
int[] buckets = new int[3];
// 우선순위 경우의 수를 모두 구함 - 순열
permutation(items, buckets, buckets.length);
return answer;
}
/**
* 순열 - 연산자 우선순위 경우의 수를 모두 구함
* @param items
* @param buckets
* @param k
*/
public static void permutation(int[] items, int[] buckets, int k) {
if (k == 0) {
// 연산자 우선순위와 중위표기법을 이용하여 후위표기법 생성
String[] infix = postfixToInfix(postfix, buckets);
// 후위표기법 계산 결과
long result = getInfixResult(infix);
// 가장 큰 값을 answer에 대입
answer = Math.max(answer, result);
return;
}
int lastIndex = buckets.length - k - 1;
for (int i = 0; i < items.length; i++) {
boolean flag = true;
for (int j = 0; j <= lastIndex; j++) {
if (buckets[j] == items[i]) {
flag = false;
}
}
if (flag) {
buckets[lastIndex + 1] = items[i];
permutation(items, buckets, k - 1);
}
}
}
/**
* 중위 표기법 -> 후위 표기법으로 변환
* @param postfix
* @param priorities
* @return
*/
public static String[] postfixToInfix(String postfix, int[] priorities) {
// String을 배열로 변환
String[] postfixArray = strToArray(postfix);
String[] infixArray = new String[postfixArray.length];
String[] op = {"+", "-", "*"};
Stack<String> stack = new Stack<>();
int index = 0;
for (int i = 0; i < postfixArray.length; i++) {
// 배열의 원소가 연산자이면
if (Arrays.asList(op).contains(postfixArray[i])) {
// 스택이 비어있으면
if (stack.isEmpty()) {
// 연산자를 push
stack.push(postfixArray[i]);
} else {
// 스택이 비어있지 않다면
// 스택에 먼저 들어있는 연산자들이 현재 연산자보다 우선순위가 높다면 pop
while (!stack.isEmpty() && compareToOperation(postfixArray[i], stack.peek(), priorities)) {
// 후위표기법 계산식에 스택에서 pop한 연산자 출력
infixArray[index++] = stack.pop();
}
// 현재 연산자를 스택에 push
stack.push(postfixArray[i]);
}
// 피연산자이면 후위표기법 계산식에 바로 출력
} else {
infixArray[index++] = postfixArray[i];
}
}
// 스택에 남아있던 연산자들 모두 후위표기법 계산식에 pop하여 출력
while (!stack.isEmpty()) {
infixArray[index++] = stack.pop();
}
return infixArray;
}
public static String[] strToArray(String postfix) {
String[] numStrArray = postfix.replaceAll("[^0-9]", " ").split(" ");
String[] opStrArray = postfix.replaceAll("[^[+]-[*]]", "").split("");
String[] result = new String[numStrArray.length + opStrArray.length];
int index = 0;
for (int i = 0; i < numStrArray.length; i++) {
result[index++] = numStrArray[i];
if (i != numStrArray.length - 1) {
result[index++] = opStrArray[i];
}
}
return result;
}
/**
* 연산자 우선순위 체크 로직
* @param op1
* @param op2
* @param priorities
* @return
*/
public static boolean compareToOperation(String op1, String op2, int[] priorities) {
String[] op = {"+", "-", "*"};
if (op1.equals(op[priorities[0]])) {
if (op2.equals(op[priorities[0]])) {
return true;
}
}
if (op1.equals(op[priorities[1]])) {
if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]])) {
return true;
}
}
if (op1.equals(op[priorities[2]])) {
if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]]) || op2.equals(op[priorities[2]])) {
return true;
}
}
return false;
}
/**
* 후위 표기법 계산 메서드
* @param infix
* @return
*/
public static long getInfixResult(String[] infix) {
long answer = 0;
String[] op = {"+", "-", "*"};
Stack<String> stack = new Stack<>();
for (int i = 0; i < infix.length; i++) {
// 후위표기법의 현재 원소가 '연산자'인 경우
if (Arrays.asList(op).contains(infix[i])) {
String operation = infix[i];
// 스택에서 피연산자들 2개를 pop
long second = Long.parseLong(stack.pop());
long first = Long.parseLong(stack.pop());
// 현재 원소의 종류에 따라 피연산자들을 계산한 결과값을 스택에 push
switch (operation) {
case "+":
stack.push(String.valueOf(first + second));
break;
case "-":
stack.push(String.valueOf(first - second));
break;
case "*":
stack.push(String.valueOf(first * second));
break;
case "/":
stack.push(String.valueOf(first / second));
break;
}
// 현재 원소가 피연산자이면 스택에 push
} else {
stack.push(infix[i]);
}
}
answer = Math.abs(Long.parseLong(stack.pop()));
return answer;
}
}
