[백준] 12845 모두의 마블 - 그리디(Greedy, 탐욕법) JAVA

https://www.acmicpc.net/problem/12845

코드설명

그리디(Greedy, 탐욕법) 입니다.

 

처음에 문제를 보면, 완전탐색이 가장 먼저 떠오릅니다.

하지만, N을 보면 1,000 입니다. 완전탐색으로 시간복잡도를 계산해보면 (N-1)! 입니다(물론, 카드의 양옆만 가능하기에 경우의 수가 훨씬 줄어들지만, 1000! 일경우에는 아무리 줄어들어도 시간초과가 발생합니다.). 팩토리얼 연산은 N^2 보다도 훨씬 빠른 속도로 증가하기 때문에 그렇습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static int[] cache;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int maxLevelNum = 0; int maxLevelIdx = -1;        
        ArrayList<Integer> arrList = new ArrayList<>();
        arr = new int[N];
        for(int i=0;i<N; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	if(maxLevelNum < arr[i]) {
        		maxLevelIdx = i;
        		maxLevelNum = arr[i];
        	}
        	arrList.add(arr[i]);
        }
        
        //그냥 가장 큰 숫자를 기준으로 하면 될듯?
        while(arrList.size() > 1) {
        	
        	//arrList의 왼쪽이 남아있다면,
        	if(maxLevelIdx > 0) {
        		int leftLevelIdx = maxLevelIdx - 1;
        		int leftLevelNum = arrList.get(leftLevelIdx);
        		answer += arrList.get(maxLevelIdx) + arrList.get(leftLevelIdx);
        		arrList.remove(leftLevelIdx);
        		maxLevelIdx--;
        	}
        	
        	//arrList의 오른쪽이 남아있다면
        	else if(maxLevelIdx < N - 1) {
        		int rightLevelIdx = maxLevelIdx + 1;
        		int rightLevelNum = arrList.get(rightLevelIdx);
        		answer += arrList.get(maxLevelIdx) + arrList.get(rightLevelIdx);
        		arrList.remove(rightLevelIdx);
        	}
        	
        }
        
        System.out.println(answer);
        
    }
    
}

 

추가로, 다른분들의 코드도 살펴보았는데, 효율적인 코드는 사실상 최대값을 기준으로 왼쪽의 모든값을 더하고, 오른쪽의 모든값을 더한 값을 반환하면 정답입니다. (저는, 실제로 arrList에 값을 remove 하는 과정이 있기에 시간이 더 소요됩니다.)