잡다한 배똥월드

728x90
코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가? O
본인의 실력으로 풀었는가? O

 

 

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

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과

programmers.co.kr

 

 

 

 

 

import java.util.*;

class Solution {
    boolean[] check; //방문 여부 체크용
    char[] list; //* + -가 들어있는 리스트
    long answer; //리턴용
    public long solution(String expression) {
        answer = 0;
        
       	//숫자들 모아놓을 배열
        ArrayList<Long> numbers = new ArrayList<>();
        //숫자 구분용
        String[] nTemp = expression.split("\\*|\\-|\\+");
        
        //숫자로 변환
        for (int i = 0; i < nTemp.length; i++) {
            numbers.add(Long.parseLong(nTemp[i]));
        }
        
        //연산기호 구분용
        char[] sTemp = expression.toCharArray();
       	
        //연산기호 담길 배열
        ArrayList<Character> sign = new ArrayList<>(); 
        
        //* + -면 추가
        for (int i = 0; i < sTemp.length; i++) {
            if (sTemp[i] == '*' || sTemp[i] == '+' || sTemp[i] == '-') {
                sign.add(sTemp[i]);
            }
        }
        
        check = new boolean[3];
        list = new char[]{'*', '+', '-'};
        
        //함수 호출
        func(numbers, sign);
        
        return answer;
    }
    
    public void func(ArrayList<Long> numbers, ArrayList<Character> sign) {
    	//다 계산 끝나면 숫자 하나만 남기 때문에 조건문이 이럼
        if (numbers.size() == 1 && sign.size() == 0) {
            //절대값으로 변환한 숫자와 answer와 비교해서 큰 쪽 담기
            answer = Math.max(answer, Math.abs(numbers.get(0)));
            return;
        } 
        
        //* + -을 for문으로 방문함
        for (int i = 0; i < list.length; i++) {
            if (check[i]) continue;
            
            check[i] = true;
            
            ArrayList<Long> numClone = (ArrayList<Long>) numbers.clone();
            ArrayList<Character> signClone = (ArrayList<Character>) sign.clone();
            
            while(signClone.indexOf(list[i]) != -1) {
                int p = signClone.indexOf(list[i]);
                
                long a = numClone.remove(p);
                long b = numClone.remove(p);
                signClone.remove(p);
                
                long c = (i == 0) ? a * b : (i == 1) ? a + b : a - b;
                numClone.add(p, c);
            }
            
            func(numClone, signClone);
            check[i] = false;
        }
    }
}

 

테스트 1 통과 (0.38ms, 75.3MB)
테스트 2 통과 (0.39ms, 72.9MB)
테스트 3 통과 (0.42ms, 76.3MB)
테스트 4 통과 (0.72ms, 75.1MB)
테스트 5 통과 (0.56ms, 68.5MB)
테스트 6 통과 (0.83ms, 75.3MB)
테스트 7 통과 (0.83ms, 71.6MB)
테스트 8 통과 (0.75ms, 74MB)
테스트 9 통과 (0.92ms, 71.4MB)
테스트 10 통과 (0.89ms, 73.1MB)
테스트 11 통과 (0.73ms, 75.4MB)
테스트 12 통과 (0.87ms, 73.6MB)
테스트 13 통과 (1.22ms, 74.3MB)
테스트 14 통과 (1.33ms, 91.1MB)
테스트 15 통과 (2.72ms, 72.3MB)
테스트 16 통과 (0.51ms, 69.9MB)
테스트 17 통과 (0.72ms, 77.8MB)
테스트 18 통과 (0.51ms, 74.5MB)
테스트 19 통과 (0.57ms, 74.4MB)
테스트 20 통과 (0.59ms, 87.8MB)
테스트 21 통과 (1.02ms, 72.8MB)
테스트 22 통과 (1.50ms, 76MB)
테스트 23 통과 (0.42ms, 75.1MB)
테스트 24 통과 (1.14ms, 69.6MB)
테스트 25 통과 (1.00ms, 73MB)
테스트 26 통과 (0.40ms, 72.7MB)
테스트 27 통과 (1.44ms, 74.2MB)
테스트 28 통과 (1.34ms, 73.3MB)
테스트 29 통과 (0.98ms, 71.8MB)
테스트 30 통과 (1.40ms, 76.4MB)

 

 

 

 

 

중요한 포인트는 split( )을 이용해서 *, +, - 를 구분해서 숫자만 골라낼 때 그냥 "*|+|-"가 아닌 "\\*|\\+|\\-"로 입력을 해야 함

 

 

 

 

 

 

728x90

+ Recent posts