본문 바로가기
JAVA/Coding Test Study

[Lv.2] 수식 최대화 : Java

by ♡˖GYURI˖♡ 2024. 3. 27.
728x90
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

이해하기

처음 들었던 생각은 완전 탐색을 해야겠으니 dfs를 써야겠다. 이거 전에 풀었던 피로도 문제랑 비슷하게 풀면 되겠네~ 였다. (그리고 풀이 실패)

 

[Lv.2] 피로도 : Java

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이해하

newbie-in-softengineering.tistory.com

 

 

이번에 참고한 블로그는 아래!

 

[level2] 프로그래머스 - 수식 최대화(JAVA)

[ 문제 풀이 ] 1. 연산자 우선순위로 가능한 우선순위를 배열로 만든다. String op[][] = { { "+", "-", "*" }, { "+", "*", "-" }, { "-", "*", "+" }, { "-", "+", "*" }, { "*", "-", "+" }, { "*", "+", "-" } }; 2. 문자열에서 숫자와

jisunshine.tistory.com

이 분의 풀이는 다음과 같다.

  1. 연산자 순서를 전부 배열로 만들어둔다.
  2. 문자열에서 숫자와 연산자를 분리하여 ArrayList에 추가
    1. 연산자를 만나면, 앞은 숫자이므로 먼저 추가
    2. 연산자 추가
    3. 1, 2번만 for문에서 수행하므로 마지막 숫자까지 추가!
  3. 미리 만들어둔 연산자 우선순위 6개 경우에 대해 계산한다.
  4. list에서 op[i][k]에 해당하는 수식을 만나면 자신의 앞의 숫자와 뒤의 숫자를 계산해준 후, 계산한 숫자로 앞의 숫자를 바꾼다. (자신과 다음 위치 숫자 제거)
  5. 수식 계산이 끝나면 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