[틀림] [자바] 프로그래머스 수식최대화 // 문자열, 구현, 링크드리스트

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

프로그래머스

* 시도1

배열에 숫자, 연산자를 넣고

갱신을 어떻게 할건지 문제발생, 해당 연산자가 있으면, i, i+1 배열의 값을 바꿔주는 방식?

값전파문제 발생 , 완료된 연산자의경우 , i+1을 i 값으로 채워주기?

끝나면 마지막 남은숫자가 정답?

맨 처음에는 삭제가 쉬운 링크드 리스트로 해볼까 생각은 했음.

but, 복잡할것 같아서 배열의 값을 바꾸는 방법으로 시도해봄

실패

 

* 풀이

그냥 ArrayList를 쓰던지, LinkedList를 쓰던지 실제 삭제를 해주면 되는거였음

제공하는 remove api 가 사기임

시간복잡도 채점을 안하는 문제는 그냥 풀어보자.

v : 숫자배열

v2 : 연산자배열

for(v2 배열)

계산후, v.remove(i+1)

v2.remove(i)

i-- // 연산자배열이 1칸 줄었으므로

import java.util.*;
class Solution {
    static HashMap<Integer,Character> m = new HashMap<>();
    static LinkedList<Long> v = new LinkedList<>();    // ArrayList에서 LinkedList로 변경
    static LinkedList<Character> v2 = new LinkedList<>();  // ArrayList에서 LinkedList로 변경
    static boolean[] vis = new boolean [104];
    static long ret;
    
    void go(char c){
        for(int i=0; i<v2.size(); i++){
            if(v2.get(i)==c){
                long a = v.get(i);
                long b = v.get(i+1);
                
                if(c=='+'){
                    v.set(i, a+b);
                } else if(c=='-'){
                    v.set(i, a-b);
                } else if(c=='*'){
                    v.set(i, a*b);
                }
                
                // LinkedList에서는 remove 메서드가 O(1)로 동작하므로 별도의 이동 로직 없이 직접 제거
                v.remove(i+1);
                v2.remove(i);
                
                // 인덱스 조정 (연산자를 하나 처리했으므로)
                i--;
            }
        }
    }
    
    public long solution(String expression) {
        long answer = 0;
        ret = 0;
        
        // 초기화
        v.clear();
        v2.clear();
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<expression.length();++i){
            if(expression.charAt(i)=='-' || expression.charAt(i)=='*' || expression.charAt(i)=='+'){
                v.add(Long.parseLong(sb.toString()));
                sb.setLength(0);
                v2.add(expression.charAt(i));
                continue;
            }
            sb.append(expression.charAt(i));
        }
        v.add(Long.parseLong(sb.toString())); //남은숫자
        
        LinkedList<Long> origin = new LinkedList<>(v);
        LinkedList<Character> origin2 = new LinkedList<>(v2);
        
        // 첫 번째 경우: * + -
        v = new LinkedList<>(origin);
        v2 = new LinkedList<>(origin2);
        Arrays.fill(vis, false);
        go('*');
        go('+');
        go('-');
        ret = Math.max(ret, Math.abs(v.getFirst()));  // get(0) 대신 getFirst() 사용
        
        // 두 번째 경우: * - +
        v = new LinkedList<>(origin);
        v2 = new LinkedList<>(origin2);
        Arrays.fill(vis, false);
        go('*');
        go('-');
        go('+');
        ret = Math.max(ret, Math.abs(v.getFirst()));
        
        // 세 번째 경우: + * -
        v = new LinkedList<>(origin);
        v2 = new LinkedList<>(origin2);
        Arrays.fill(vis, false);
        go('+');
        go('*');
        go('-');
        ret = Math.max(ret, Math.abs(v.getFirst()));
        
        // 네 번째 경우: + - *
        v = new LinkedList<>(origin);
        v2 = new LinkedList<>(origin2);
        Arrays.fill(vis, false);
        go('+');
        go('-');
        go('*');
        ret = Math.max(ret, Math.abs(v.getFirst()));
        
        // 다섯 번째 경우: - + *
        v = new LinkedList<>(origin);
        v2 = new LinkedList<>(origin2);
        Arrays.fill(vis, false);
        go('-');
        go('+');
        go('*');
        ret = Math.max(ret, Math.abs(v.getFirst()));
        
        // 여섯 번째 경우: - * +
        v = new LinkedList<>(origin);
        v2 = new LinkedList<>(origin2);
        Arrays.fill(vis, false);
        go('-');
        go('*');
        go('+');
        ret = Math.max(ret, Math.abs(v.getFirst()));
        
        return ret;
    }
}

ArrayList를 써도 정답은 같다.

import java.util.*;
class Solution {

    static ArrayList<Long> v = new ArrayList<>();    // int에서 long으로 변경
    static ArrayList<Character> v2 = new ArrayList<>();
    static boolean[] vis = new boolean [104];
    static long ret;    // int에서 long으로 변경
    
    void go(char c){
        // 수정된 go 메서드
        for(int i=0; i<v2.size(); i++){
            if(v2.get(i)==c){   // vis 체크 추가
                vis[i]=true;
                long a = v.get(i);
                long b = v.get(i+1);
                
                if(c=='+'){
                    v.set(i, a+b);
                } else if(c=='-'){
                    v.set(i, a-b);
                } else if(c=='*'){
                    v.set(i, a*b);
                }
                
                // i+1부터 끝까지 값 한 칸씩 당기기
                v.remove(i+1);
                
                // i부터 끝까지 연산자 한 칸씩 당기기
                v2.remove(i);
                
                // 인덱스 조정 (연산자를 하나 처리했으므로)
                i--;
            }
        }
    }
    
    public long solution(String expression) {
        long answer = 0;
        ret = 0;  // ret 초기화 추가
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<expression.length();++i){
            if(expression.charAt(i)=='-' || expression.charAt(i)=='*' || expression.charAt(i)=='+'){
                v.add(Long.parseLong(sb.toString()));  // Integer에서 Long으로 변경
                sb.setLength(0);
                v2.add(expression.charAt(i));
                continue;
            }
            sb.append(expression.charAt(i));
        }
        v.add(Long.parseLong(sb.toString())); //남은숫자
        
        ArrayList<Long> origin = new ArrayList<>(v);  // Integer에서 Long으로 변경
        ArrayList<Character> origin2 = new ArrayList<>(v2);  // 연산자 원본 저장 추가
        
        // 첫 번째 경우: * + -
        v = new ArrayList<>(origin);
        v2 = new ArrayList<>(origin2);
        Arrays.fill(vis, false);
        go('*');
        go('+');
        go('-');
        ret = Math.max(ret, Math.abs(v.get(0)));  // v의 마지막이 아닌 첫 번째 요소 사용
        
        // 두 번째 경우: * - +
        v = new ArrayList<>(origin);
        v2 = new ArrayList<>(origin2);
        Arrays.fill(vis, false);
        go('*');
        go('-');
        go('+');
        ret = Math.max(ret, Math.abs(v.get(0)));
        
        // 세 번째 경우: + * -
        v = new ArrayList<>(origin);
        v2 = new ArrayList<>(origin2);
        Arrays.fill(vis, false);
        go('+');
        go('*');
        go('-');
        ret = Math.max(ret, Math.abs(v.get(0)));
        
        // 네 번째 경우: + - *
        v = new ArrayList<>(origin);
        v2 = new ArrayList<>(origin2);
        Arrays.fill(vis, false);
        go('+');
        go('-');
        go('*');
        ret = Math.max(ret, Math.abs(v.get(0)));
        
        // 다섯 번째 경우: - + *
        v = new ArrayList<>(origin);
        v2 = new ArrayList<>(origin2);
        Arrays.fill(vis, false);
        go('-');
        go('+');
        go('*');
        ret = Math.max(ret, Math.abs(v.get(0)));
        
        // 여섯 번째 경우: - * +
        v = new ArrayList<>(origin);
        v2 = new ArrayList<>(origin2);
        Arrays.fill(vis, false);
        go('-');
        go('*');
        go('+');
        ret = Math.max(ret, Math.abs(v.get(0)));
        
        return ret;
    }
}