[JAVA] 프로그래머스 LEVEL2 수식 최대화

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

코딩테스트 연습 > 2020 카카오 인턴십 > 수식 최대화

 

난이도: LEVEL2

알고리즘 유형: 구현 

 

정답 코드1

init 메서드

연산자와 피연산자를 구별해서 각각 리스트에 저장

 

combination 메서드

* / + / - 3가지 연산자의 우선순위를 백트래킹을 통해서 구하기 총 3! 결과가 나온다.

 

calculate 메서드

combination 메서드를 통해서 받은 우선순위를 바탕으로 연산을 하고 계산

이때 리스트의 사용한 값을 삭제하면서 진행하는데 

 

아쉬운점 

ArrayList remove 같은 경우 삭제 이전 index는 그대로 활용 이후 index는 삭제하고 다시 채워 넣기 때문에 상당히 시간 소요를 많이하는 작업이다. 

 

import java.util.*;
class Solution {
    static ArrayList<Long> list = new ArrayList<>();  // 숫자 저장 
    static ArrayList<String> cal = new ArrayList<>(); // 연산 저장 
    static String [] sequence = new String [3];       // 순서 저장 
    static String [] calculation = {"*", "+", "-"};   // 연산자들 
    static boolean [] visited = new boolean [3];
    public static long answer = 0;
    public long solution(String expression) {
        init(expression);
        combination(0);
        return answer;
    }
    public static void combination(int depth){ // 조합 짜기 결과: 3! 
        if(depth == 3){
            calculate();
            return;
        }
        for(int i = 0; i < 3; i++){
            if(visited[i]) continue;
            visited[i] = true;
            sequence[depth] = calculation[i];
            combination(depth + 1);
            visited[i] = false;
        }
    }
    public static void calculate(){ // 계산 
         ArrayList<Long> nums = new ArrayList<>(list);
         ArrayList<String> cals = new ArrayList<>(cal);
         while(!cals.isEmpty()){
             int idx = -1;
             String target = null;
             if(idx == -1){
                 idx = cals.indexOf(sequence[0]);
                 target = sequence[0];
             }
             if(idx == -1){
                 idx = cals.indexOf(sequence[1]);
                 target = sequence[1];
             }
             if(idx == -1){
                 idx = cals.indexOf(sequence[2]);
                 target = sequence[2];
             }
             if(idx == -1) break;
              
             long tar1 = nums.get(idx);
             long tar2 = nums.get(idx + 1);
             
             cals.remove(idx);
             nums.remove(idx + 1);
             
             long result = 0;
             
             if(target.equals("*")){
                result = tar1 * tar2;    
             }
             else if(target.equals("+")){
                result = tar1 + tar2;    
             }
             else{
                result = tar1 - tar2;    
             }
             nums.set(idx, result);
         }
         long sum = 0;
         for(int i = 0; i < nums.size(); i++){
             sum += nums.get(i);
         }
         answer = Math.max(Math.abs(sum), answer);
    }
    public static void init(String expression){ // init 연산자, 피연산자 분리 
        int idx = 0;
        for(int i = 0; i < expression.length(); i++){
            char cur = expression.charAt(i);
            if(cur == '*' || cur == '+' || cur == '-'){
                list.add(Long.parseLong(expression.substring(idx, i)));
                cal.add(String.valueOf(cur));  
                idx = i + 1;
            }
        }
        // 마지막 숫자 
        list.add(Long.parseLong(expression.substring(idx, expression.length())));
    }
}

정답 코드2

정답 코드1을 개선

리스트 안에서 삭제가 아닌 노드형식으로 데이터를 배열에 저장하고

이전 인덱스 다음 인덱스를 업데이트 하는 방식으로 진행 

 

막혔던 부분 

Node 객체 자체를 배열에 저장을 하기 때문에 

NodeArray에서 nodes 배열로 복사하여 저장하고 배열에 있는 객체를 수정하면 원본 객체 또한 수정된다. 

이렇게 똑같은 인스턴스 변수를 가지는 인스턴스를 생성하고 해당 데이터를 nodes 배열에 다시 저장하는 방식으로 해결 

Node [] nodes = new Node[nodeArray.length];
for(int i = 0; i < nodes.length; i++){
    Node save = nodeArray[i];
    Node copy = new Node();
    copy.self = save.self;
    copy.previous = save.previous;
    copy.next = save.next;
    copy.calculation = save.calculation;
    copy.num = save.num;
    nodes[i] = copy;
}

 

 

import java.util.*;
class Solution {
    static class Node { // 연산자 / 피연산자 모두 담는다. 
        int self = -1;
        int previous = -1; // 이전 index 
        int next = -1; // 다음 index 
        String calculation; // 연산자 
        long num; // 숫자 
        @Override
        public String toString(){
            return previous + " " + self + " " + next + " " + calculation + " " + num;
        }
    }
    static Node [] nodeArray;
    static String [] sequence = new String [3];       // 순서 저장 
    static String [] calculation = {"*", "+", "-"};   // 연산자들 
    static boolean [] visited = new boolean [3];
    public static long answer = 0;
    public long solution(String expression) {
        init(expression);
        combination(0);
        return answer;
    }
    public static void combination(int depth){ // 조합 짜기 결과: 3! 
        if(depth == 3){
            calculate();
            return;
        }
        for(int i = 0; i < 3; i++){
            if(visited[i]) continue;
            visited[i] = true;
            sequence[depth] = calculation[i];
            combination(depth + 1);
            visited[i] = false;
        }
    }
    public static void calculate(){ // 계산 
        Node [] nodes = new Node[nodeArray.length];
        for(int i = 0; i < nodes.length; i++){
            Node save = nodeArray[i];
            Node copy = new Node();
            copy.self = save.self;
            copy.previous = save.previous;
            copy.next = save.next;
            copy.calculation = save.calculation;
            copy.num = save.num;
            nodes[i] = copy;
        } 
        for(int i = 0; i < 3; i++){
            String target = sequence[i]; // 이번 연산자 
            int idx = 0;
            while(idx != -1){
                Node node = nodes[idx];
                // 검사 방식 연산자 != null && 이번 순위 연산자인지  
                if(node.calculation != null && node.calculation.equals(target)){ 
                     Node preNode = nodes[node.previous]; // 이전 피연산자
                     Node nextNode = nodes[node.next]; // 이후 피연산자 
                     long result = 0;
                     if(target.equals("*")){
                         result = preNode.num * nextNode.num;
                     }
                     else if(target.equals("+")){
                         result = preNode.num + nextNode.num;
                     }
                     else{ // -
                         result = preNode.num - nextNode.num;
                     }
                     // 0 (1) 2 (3) 4 
                     preNode.next = nextNode.next;
                     preNode.num = result;
                     
                     if(preNode.next != -1){
                          Node updateNextNode = nodes[preNode.next];
                          updateNextNode.previous = node.previous;
                     }
                      
                     idx = preNode.next;
                } 
                else{
                    idx = node.next;
                }
            }
        }
        long sum = 0;
        int idx = 0;
        while(idx != -1){ // 다음 노드가 없으면 stop
            Node node = nodes[idx];
            sum += node.num;
            idx = node.next;
        }
        answer = Math.max(answer, Math.abs(sum));
    }
    public static void init(String expression){ // init 연산자, 피연산자 분리 
        int idx = 0;
        ArrayList<Node> nodes = new ArrayList<>();
        for(int i = 0; i < expression.length(); i++){
            char cur = expression.charAt(i);
            if(cur == '*' || cur == '+' || cur == '-'){
                // 피연산자 
                long num = (Long.parseLong(expression.substring(idx, i)));
                Node node = new Node();
                node.num = num;
                nodes.add(node);
                // 연산자 
                Node node2 = new Node();
                node2.calculation = String.valueOf(cur);
                nodes.add(node2);
                idx = i + 1;
            }
        }
        // 마지막 숫자 
        long num = (Long.parseLong(expression.substring(idx, expression.length())));
        Node node = new Node();
        node.num = num;
        nodes.add(node);
        nodeArray = new Node [nodes.size()];
        
        for(int i = 0; i < nodes.size(); i++){ // 리스트 -> 배열 + previous next 채우기 
            Node temp = nodes.get(i);
            temp.self = i;
            if(i != nodes.size() - 1){
                temp.next = i + 1;
            } 
            if(i != 0){
                temp.previous = i - 1; 
            }
            nodeArray[i] = temp;
        }
    }
}