[2020 카카오 인턴십] 수식 최대화(Java, 문자열 처리, ArrayList For문 내 원소 삭제)

programmers.co.kr/learn/courses/30/lessons/67257

코딩테스트 연습 - 수식 최대화

 

 

 

## 접근

---

• 처음에 시행착오를 겪었던 것은, 문자열 내에서 모든 걸 조작하려고 했다. replace를 사용해서 코드를 작성해보니 '-'가 붙어있는 것이 연산용도인지 음수를 나타내는지 확인이 불가능해지고 코드가 더러워진다.
  
  
  
  
  
• 주변 코드를 참고해, 피연산자와 연산자를 구분해 자료구조에 넣기로 했다. 여기서, 배열을 사용하지 말고, ArrayList를 사용해야 한다. ArrayList는 원소의 삭제와 삽입이 간편하므로 문제를 쉽게 풀 수 있다. 
  
  
  
• 피연산자와 연산자를 자료구조에 넣어주고, 자료구조의 원소들을 순차적으로 접근한다. 가장 중요한 것은 for문내에서 원소를 삭제할 때 주의해야 한다. for문내 선언된 변수들을 주목해서 코드를 보도록 한다. remove 연산이 이루어지면서, 바껴진 자료구조의 길이와 탐색 인덱스는 뺄셈 연산을 통해서 조정해주면 된다. 
  
  # 원칙적으론, iterator를 통해서 remove 연산이 이루어지지만, 이 문제는 인덱스를 통해서 앞과 뒤의 값들을 확인해야 하므로 for문을 통해서 해결하는 것이 편하다.

 

 

 

 

## 해설코드

---

import java.util.*;
import java.io.*;
 
class Solution {
    int[] order;
    String[] sArr = {"*", "+", "-"};
    ArrayList<String> aList;
    boolean[] chk;
    long answer = 0;
    long result = 0;
    
    boolean isDigit(char c){
        if(c >= '0' && c <= '9')
            return true;
        else
            return false;
    }
    
    void perm(int idx){
        if(idx == 3){
            ArrayList<String> list = new ArrayList<>(aList);
            
            for(int i = 0; i < order.length; i++){
                int size = list.size();
                for(int j = 0; j < size; j++){
                    if(list.get(j).equals(sArr[order[i]])){
                        Long num1 = Long.valueOf(list.get(j - 1));
                        Long num2 = Long.valueOf(list.get(j + 1));
                        Long result = Long.valueOf(0);
                        
                        if(sArr[order[i]].equals("+")){
                            result = num1 + num2;
                        }else if(sArr[order[i]].equals("-")){
                            result = num1 - num2;
                        }else if(sArr[order[i]].equals("*")){
                            result = num1 * num2;
                        }
                        
                        for(int t = 0; t < 3; t++)
                            list.remove(j - 1);
                    
                        list.add(j - 1, String.valueOf(result));
                        size -= 2;
                        j -= 1;
                    }
                }
            }
            
            answer = Math.max(answer, Math.abs(Long.valueOf(list.get(0))));
        }
        
        for(int i = 0; i < 3; i++){
            if(!chk[i]){
                order[idx] = i;
                
                chk[i] = true;
                perm(idx + 1);
                chk[i] = false;
            }
        }
    }
    
    public long solution(String expression) {
        order = new int[3];
        chk = new boolean[3];
        aList = new ArrayList<>();
        
        int start = 0;
        for(int i = 0; i < expression.length(); i++){
            if(expression.charAt(i) == '*' || 
              expression.charAt(i) == '-' ||
              expression.charAt(i) == '+'){
                aList.add(expression.substring(start, i));
                aList.add(String.valueOf(expression.charAt(i)));
                start = i + 1;
            }
        }
        aList.add(expression.substring(start));
 
        perm(0);
        
        return answer;
    }
}