[백준] 11501 주식 - 탐욕법(Greedy, 그리디) + 우선순위큐(PriorityQueue)JAVA

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

11501번: 주식

코드설명

그리디 알고리즘입니다.

처음에는 단순한 구현처럼 보이지만, 문제에 대한 아이디어가 있어야 풀 수 있습니다.

 

만약 앞에서부터 맨 뒤까지 최대값을 순회하여 구한다면 시간복잡도는 O(N^2) 이므로 시간초과가 납니다.

N의 조건은 자연수 N(2 ≤ N ≤ 1,000,000) 입니다.

 

만약 뒤에서부터 연산을 시작하면, O(N) 으로 시간복잡도를 변경시킬 수 있습니다.

 

예시를 들어보겠습니다.

1
5
1 1 3 1 2

1. [1 , 1 , 3 , 1 , 2] 에서 맨 뒤의 2부터 앞으로 이동시키며 진행시켜보겠습니다.

1-1.max  = 0, arr[4] = 2 이므로, max = 2 로 변경됩니다.

1-2 max = 2, arr[3] = 1 이므로, max > arr[3] 이기에  answer += 1

1-3.max =2, arr[2] = 3 이므로, max = 3 으로 변경됩니다.

1-4.max=3, arr[1] = 1 이므로, max > arr[1] 이기에 answer += 2 

1-5.max=3, arr[0] = 1 이므로, max > arr[0] 이기에 answer += 2 

answer = 5 가 나옵니다.

 

위의 로직을 확인해보면 O(N)의 시간복잡도임을 확인할 수 있습니다.

 

아래는 이 문제와 비슷한 로직의 문제입니다.

https://passionfruit200.tistory.com/5

[백준] 13305번 주유소 - 그리디(Greedy, 탐욕법) JAVA

이 주유소 문제의 경우 앞에서부터 가장 효율적인 주유를 위해 처리하는 방식이고,

아래의 경우는 뒤에서부터 가장 효율적인 투자를 처리하는 방식입니다. (앞에서부터 처리할경우에는 불필요한 자료구조들이 필요합니다.)

연산의 순서를 바꾸는것만으로도 매우 빠르게 해결할 수 있습니다.

코드

뒤에서부터 확인하며, max값을 바로바로 확인하는 코드( 시간복잡도 O(N) )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int T, N;
	public static int[] arr;
	public static long answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int i = 0;i < T; i++) {
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		answer = 0;
    		arr = new int[N];
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[j] = Integer.parseInt(st.nextToken()); 
    		}
    		
    		long maxValue = 0;
    		for(int j=N-1; j>=0;j--) {
    			if(maxValue < arr[j]) {
    				maxValue = arr[j];
    			}else {
    				answer += maxValue - arr[j];
    			}
    		}
    		
    		System.out.println(answer);
    	}	
    }
    
}

 

정답코드 2 입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int[] arr;
	static int answer = 0;
	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());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			arr = new int[N];
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N;i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			sb.append(stock()).append("\n");
		}
		System.out.println(sb.toString());
		
	}
	
	static long stock() {
		long max = arr[N-1];
		long profit = 0;
		for(int i=N-1; i>=0; i--) {
			if(arr[i] <= max) {
				profit += max - arr[i];
			}else if(arr[i] > max) {
				max = arr[i];
			}
		}
		return profit;
	}
	
}

 

우선순위큐를 활용한 경우(여전히 시간초과가 발생한다)

시간복잡도는 우선순위큐는 삽입시에 log N 이고, N번 반복하니 N log N 입니다.

삭제시에는 log N 의 시간복잡도입니다.

총 시간복잡도는 O(T N log N ) 입니다. T = 개수가 안나와있음, N = 10^6 인데,

log_2(10^6) = 19.931568569324 입니다. (알고리즘 상에서 log의 밑은 일반적으로 2입니다. (10이 아님)).

여기서 T가 조금이라도 10^2 보다도 더 커진다면 바로 시간초과가 나오므로 시간초과가 발생하는 것 같습니다.

 

그리고 아래 코드 구현시에 해당하지 않는 pq값을 반드시 remove 해주어야 이후의 연산에 영향을 미치지 않습니다. ( 처음에 해당 부분 놓쳐서 반례가 틀렸습니다.)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static long[] arr;
	static int answer = 0;
	static PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
	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());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			arr = new long[N];
			st = new StringTokenizer(br.readLine());
			pq.clear();
			for(int i=0;i<N;i++) {
				arr[i] = Long.parseLong(st.nextToken());
				pq.offer(arr[i]);
			}
			
			sb.append(stock()).append("\n");
		}
		System.out.println(sb.toString());
		
	}
	
	static long stock() {
		long cost = 0; //구매하는데 사용한 금액
		long cnt = 0;
		long profit = 0; // 이익
		for(int i=0;i<N; i++) {
			cost += arr[i];
			cnt += 1;
			
			//만약, 가장 최대값과 같다면, 
			if(arr[i] == pq.peek()) {
				profit += arr[i] * cnt - cost;
				cost = 0;
				cnt = 0;
			}
			pq.remove(arr[i]);
		}
		return profit;
	}
	
	
}

 

시간복잡도 O(N^2) 인 코드 ( 시간초과 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int T, N;
	public static int[] arr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int i = 0;i < T; i++) {
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		answer = 0;
    		arr = new int[N];
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[j] = Integer.parseInt(st.nextToken()); 
    		}
    		
    		for(int j=0;j<N;j++) {
    			int standard = arr[j];
    			int maxValue = 0;
    			for(int k=j + 1; k<N;k++) {
    				if(maxValue < arr[k] ) {
    					maxValue = arr[k];
    				}
    			}
    			if(maxValue > arr[j]) { //만약 최대값보다 작다면 해당 주식 구매하고 판매.
    				
    				answer += maxValue - standard;
    			} 
    		}
    		System.out.println(answer);
    	}	
    }
    
}