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

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DFS

 

먼저, 문자열 expression을 숫자와 연산자로 나눠 각각 배열에 저장한다.

 - 숫자인 경우, 숫자를 나타내는 임시 문자열에 하나씩 값을 붙여둔다.

- 연산자인 경우, 여태까지 구한 임시 문자열을 숫자로 변환해 숫자 리스트에 저장하고, 임시 문자열을 초기화한다. 그리고 연산자 리스트에도 현재 연산자를 추가한다. + 반복문이 끝나면 마지막으로 만들어진 문자도 따로 삽입해주는 것을 잊지 말자,,

static List<Long> numList = new LinkedList<>();         // 숫자 담을 리스트
static List<Character> operList = new LinkedList<>();   // 연산자 담을 리스트

static long answer = 0;

public long solution(String expression) {        
    String tmpNum = "";

    for(char c : expression.toCharArray()) {
        if(Character.isDigit(c)) {  // 숫자인 경우, 누적해서 숫자로 저장
            tmpNum += c;
        }
        else { // 연산자인 경우, 여태 앞에서 구한숫자를 숫자 리스트에 넣음
            numList.add(Long.parseLong(tmpNum));
            tmpNum = "";
            operList.add(c);
        }
    }
    numList.add(Long.parseLong(tmpNum));   // 마지막 문자 삽입

    return answer;
}

 

 

이제 (+, -, *) 3가지 원소로 만들 수 있는 모든 중복 없는 순열을 구하는 메서드를 작성한다.

private static void dfs(int depth) {
    if(depth == 3) {
        solve();
        return;
    }

    for(int i = 0 ; i < 3 ; i++) {
        if(!chk[i]) {
            chk[i] = true;
            output[depth] = oper[i];
            dfs(depth + 1);
            chk[i] = false;
        }
    }
}

 

 

순열 메서드에서 연산자 3개를 모두 골랐을 때, 우선순위에 맞게 연산을 수행하는 solve 메서드를 작성한다. 

- 복제된 연산자 리스트의 값이 현재 우선순위 연산자와 일치하는 경우, 앞뒤 숫자를 꺼내서 계산한다. 그리고 나서 앞뒤 숫자를 삭제하고, j번 위치에 연산 결과를 넣고, 연산자 리스트의 인덱스를 하나 줄인다.

 

반복문이 끝나면 남은 결과 (= 숫자 리스트에 남은 1개의 값)과 현재까지의 최댓값을 비교해 둘 중 더 큰 값으로 최댓값을 갱신한다.

private static void solve() {
    List<Long>   copyNums = new LinkedList<>();
    List<Character> copyOps = new LinkedList<>();

    copyNums.addAll(numList);
    copyOps.addAll(operList);

    for(int i = 0 ; i < output.length ; i++) {
        char nowOp = output[i];   // 현재 우선순위 연산자

        for(int j = 0 ; j < copyOps.size() ; j++) {
            if(copyOps.get(j) == nowOp) { // 현재 우선순위 연산자와 맞는 경우, 앞뒤 숫자 꺼내서 계산 후 다시 넣기
                long res = calc(copyNums.get(j), copyNums.get(j + 1), nowOp);

                copyNums.remove(j + 1);  // 숫자 삭제
                copyNums.remove(j);
                copyOps.remove(j);     // 연산자 삭제

                copyNums.add(j, res);    // j번 위치에 연산 결과 넣기

                j--;    // 삭제했으니 인덱스 하나 줄이기
            }
        }
    }

    answer = Math.max(answer, Math.abs(copyNums.get(0)));
}

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static char[] oper = {'+', '-', '*'};
    static char[] output = new char[3]; // 순열 결과 저장 배열
    static boolean[] chk = new boolean[3];
 
    static List<Long> numList = new LinkedList<>();         // 숫자 담을 리스트
    static List<Character> operList = new LinkedList<>();   // 연산자 담을 리스트
    
    static long answer = 0; // 우승 시 받을 수 잇는 가장 큰 상금 금액
        
    public long solution(String expression) {        
        String tmpNum = "";
        
        for(char c : expression.toCharArray()) {
            if(Character.isDigit(c)) { // 숫자인 경우
               tmpNum += c;
            }
            else { // 연산자인 경우
                numList.add(Long.parseLong(tmpNum));
               tmpNum = "";
                operList.add(c);
            }
        }
        numList.add(Long.parseLong(tmpNum));   // 마지막 문자 삽입
        
        dfs(0);
        return answer;
    }
    
    // 순열 만드는 메서드
    private static void dfs(int depth) {
        if(depth == 3) {
            solve();
            return;
        }
        
        for(int i = 0 ; i < 3 ; i++) {
            if(!chk[i]) {
                chk[i] = true;
                output[depth] = oper[i];
                dfs(depth + 1);
                chk[i] = false;
            }
        }
    }
    
    // 연산
    private static void solve() {
        List<Long>   copyNums = new LinkedList<>();
        List<Character> copyOps = new LinkedList<>();
                
       copyNums.addAll(numList); // 얕은 복사
        copyOps.addAll(operList);
        
        for(int i = 0 ; i < output.length ; i++) {
            char nowOp = output[i];   // 현재 우선순위 연산자
            
            for(int j = 0 ; j < copyOps.size() ; j++) {
                if(copyOps.get(j) == nowOp) { // 현재 우선순위 연산자와 맞는 경우, 앞뒤 숫자 꺼내서 계산 후 다시 넣기
                    long res = calc(copyNums.get(j), copyNums.get(j + 1), nowOp);
                    
                    copyNums.remove(j + 1);  // 숫자 삭제
                    copyNums.remove(j);
                    copyOps.remove(j);     // 연산자 삭제
                    
                    copyNums.add(j, res);    // j번 위치에 연산 결과 넣기
                    
                    j--;    // 삭제했으니 인덱스 하나 줄이기
                }
            }
        }
        
        answer = Math.max(answer, Math.abs(copyNums.get(0)));
    }
    
    // 수식 계산
    private static long calc(Long a, Long b, char c) {
        long result = 0;
        
        switch(c) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
        }
        
        return result;        
    }
}

 

 

➕ 다른 풀이 방식

🔗 참조

 

연산자 앞뒤 두 숫자 계산 방식이 다르다.리스트에서 j번째 값 하나 지우면 j+1번째 값이 j번째로 당겨져오므로 두 번 다 remove(j) 하셨다.

 

잊고 있었다.. remove(int idx)하면 삭제뿐만 아니라 삭제된 객체 리턴도 할 수 있다는 사실을!!

long tmp = calc(tmpOps.remove(j), tmpOps.remove(j), op[i]);
tmpNums.add(j, tmp);
tmpOps.remove(j);
j--;

 

---

💦 어려웠던 점

- 연산할 때 연산자 리스트와 숫자 리스트를 그대로 사용할 생각만 했지, 복사해서 사용할 생각은 하지 못 했다.

- 앞뒤 숫자를 꺼낼 때, 인덱스를 어떻게 가져오고 지울지 생각하지 못 했다.

- 연산 결과를 식에 다시 어떻게 적용시키지 하는 문제를 갖고 있었다..

- 연산자 기준으로 끊어서 연산시키는 문제는 얼마든지 나올 수 있으니까 잘 템플릿을 기억해둬야겠다,,,

 

🧐 새로 알게 된 내용

- ArrayList.addAll(Collection c) : A 리스트의 값을 B 리스트에 모두 추가 (참고)

- ArrayList.remove(int idx) : 삭제뿐만 아니라 삭제된 객체 리턴도 할 수 있다 (참고)

 

1회독	2회독	3회독	4회독	5회독
V	240403	240715

 

 

(+2회독 240403)

로직은 얼추 생각했는데 구현이 오래 걸리다...

담엔 신속하게 풀자,

 

코드 확인하기

import java.util.*;
 
class Solution {
    static char[] operands = {'+', '-', '*'};
    static boolean[] chk = new boolean[3];
    
    static List<Long> numList = new ArrayList<>();  // 숫자 리스트
    static List<Character> operList = new ArrayList<>();    // 연산자 리스트
    
    static long answer = 0;
    
    public long solution(String expression) {
        String tmp = "";
        
        for(char c : expression.toCharArray()) {
            if(Character.isDigit(c)) {
                tmp += c;
            }
            else {
                numList.add(Long.parseLong(tmp));
                tmp = "";
                operList.add(c);
            }
        }
        numList.add(Long.parseLong(tmp));    // 마지막 숫자 추가
        
        makeCombinations(0, "");
        return answer;
    }
    
    private static void makeCombinations(int cnt, String str) {
        if(cnt == 3) {
            solve(str);
            return;
        }
        
        for(int i = 0 ; i < 3 ; i++) {
            if(!chk[i]) {
                chk[i] = true;
                makeCombinations(cnt + 1, str + operands[i]);
                chk[i] = false;
            }
        }
    }
    
    private static void solve(String str) {
        List<Long> copyNums = new LinkedList<>();
        List<Character> copyOps = new LinkedList<>();
        
        copyNums.addAll(numList);
        copyOps.addAll(operList);
        
        for(int i = 0 ; i < str.length() ; i++) {
            char nowOp = str.charAt(i);
            
            for(int j = 0 ; j < copyOps.size() ; j++) {
                if(copyOps.get(j) == nowOp) {
                    long res = calc(copyNums.get(j), copyNums.get(j + 1), nowOp);
                    
                    copyNums.remove(j + 1);
                    copyNums.remove(j);
                    copyOps.remove(j);
                    
                    copyNums.add(j, res);
                    j--;
                }
            }
        }
        
        answer = Math.max(answer, Math.abs(copyNums.get(0)));
    }
    
    private static long calc(Long a, Long b, char c) {
        long result = 0;
        
        switch(c) {
            case '+':
                result = a+b;
                break;
            case '-':
                result = a-b;
                break;
            case '*':
                result = a*b;
                break;
        }
        
        return result;
    }
}

---

(참고)

프로그래머스-2020 카카오 인턴십 ( 수식 최대화 by Java )

[프로그래머스 - Java] 수식 최대화 (2020 카카오 인턴십)

[카카오 인턴] 수식 최대화 (DFS, Java, 프로그래머스)