[백준] 11399번 : ATM - JAVA [자바]

www.acmicpc.net/problem/11399

11399번: ATM

 

---

• 문제

 

 

 

이 또한 활동 선택 문제(Activity Selection Problem) 문제로 볼 수 있다. 조금만 이해하면 쉽게 풀 수 있는 문제다. 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

앞서 포스팅 했던 문제인 회의실배정과 유사한 문제다. 문제를 잘 이해해야 하는 것이 '종료 시간'이 아니라 '대기 시간의 총합'을 구하는 문제라는 점. 즉, 어떻게 배치하던 총 걸리는 같더라도, 한 사람이 대기하는 시간은 달라질 수 있다.

 

상식적으로 대기시간을 줄이려면 앞 사람이 일찍 끝내야 그만큼 대기시간을 줄일 수 있다. 그리고 각각의 사람이 돈을 인출할 때에는 다른 사람이 개입할 수 없으므로 그리디 알고리즘의 조건인 독립성과 전체 최적해가 부분 최적해를 만족함 둘 다 만족한다.

 

즉, 입력받은 각각의 인출하는데 걸리는 시간을 오름차순으로 정렬하여 대기시간을 구해주면 되는 전형적인 활동 선택 문제다. 활동 선택 문제에 대해서는 이전 포스팅에서 자세히 다루고 있으니 한 번 보고 오시는 것을 추천드린다.

st-lab.tistory.com/145

[백준] 1931번 : 회의실배정 - JAVA [자바]

 

 

알고리즘 자체는 매우 간단하다. 정렬되어있는 배열과, 이전까지의 대기시간 변수, 각 사람별 대기시간의 총합 변수 이렇게 3개를 이용하면 된다.

 

즉, 아래와 같이 짤 수 있다.

// arr[] 배열은 정렬되어있다고 가정 

int prev = 0;	// 이전까지의 대기시간 누적합 
int sum = 0;	// 사람별 대기시간 총합 
		
for(int i = 0; i < N; i++) {	
	// 이전까지의 대기시간과 현재 사람이 걸리는 시간을 더해준다.
	sum += prev + arr[i];
    
	// 이전까지의 누적합에 현재 걸리는 시간을 더해준다.
	prev += arr[i];
}

// sum 출력

 

 

i번째 사람이 돈을 인출하는데 걸리는 시간 + 이전까지의 대기시간 총합을 하면 i번째가 대기한 시간이 산출된다. 이 것을 sum변수에 더해주면 모든 사람이 돈을 인출하는데 걸렸던 대기시간의 합이 구해진다.

 

그리고 이전까지의 대기시간을 표현하기 위해 위 과정이 완료되면 prev 변수에 i번째가 돈을 인출하는데 걸렸던 시간을 더해주면 그 다음사람에 대해서는 이전까지의 대기시간이 된다. 

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

문제를 보면 알겠지만, Pi의 범위가 1 <= Pi <= 1,000 이기 때문에 배열에 넣고 Arrays.sort()을 이용하는 방법과, 카운팅 정렬(Counting Sort)을 쓰는 방법 둘 다 가능하다.

 

일단, Scanner 입력 방법에서 두 가지 정렬을 각각 테스트 하고, BufferedReader 입력 방법에서는 카운팅 정렬만 사용하여 보여주고자 한다. 즉, 아래와 같은 순서로 풀이 할 것이다.

 

1. Scanner + Arrays.sort()

2. Scanner + Counting Sort

3. BufferedReader + Counting Sort

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + Arrays.sort()]

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		// 정렬 
		Arrays.sort(arr);


		int prev = 0;	// 이전까지의 대기시간 누적합 
		int sum = 0;	// 사람별 대기시간 총합 
				
		for(int i = 0; i < N; i++) {	
			// 이전까지의 대기시간과 현재 사람이 걸리는 시간을 더해준다.
			sum += prev + arr[i];
		    
			// 이전까지의 누적합에 현재 걸리는 시간을 더해준다.
			prev += arr[i];
		}
		System.out.println(sum);
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다. 알고리즘 자체는 그리 어렵지 않으니 쉽게 이해하실 수 있을 것이다.

 

 

 

---

- 방법 2 : [Scanner + Counting Sort]

 

 

 

 

정렬 방법을 Arrays.sort() 대신 Counting Sort을 이용하여 풀이하는 방법이다. 혹시 Counting Sort에 대해 모른다면 아래 글을 읽고 오시는 것을 추천드린다.

 

st-lab.tistory.com/104

카운팅 정렬 (Counting Sort / 계수 정렬) _ Java [자바]

쉽게 생각하면 입력받은 값을 index로 활용하는 것이다. 예로들면 입력이 3이라면 index 3의 값을 1 증가시키는 것이다.

 

 

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();


		// 입력의 범위는 1 ~ 1000이므로 1001개의 index를 둔다.
		int[] arr = new int[1001];

		// Counting Sort 
		while (N-- > 0) {
			arr[in.nextInt()]++;
		}

		int prev = 0;	// 이전까지의 대기시간 누적합
		int sum = 0;	// 사람별 대기시간 총합
		
		for (int i = 0; i < 1001; i++) {
			
			// 해당 i index가 0이 될 때 까지 반복 
			while (arr[i]-- > 0) {
				// 이전까지의 대기시간과 현재 사람이 걸리는 시간을 더해준다.
				sum += (i + prev);
				
				// 이전까지의 누적합에 현재 걸리는 시간을 더해준다.
				prev += i;
			}
		}
		System.out.println(sum);
	}

}

 

 

 

이렇게 입력범위를 알면 유용하게 쓸 수 있는 것이 Counting Sort이니 알아두고 있으면 좋을 것 같다.

 

 

 

---

- 방법 3 : [BufferedReader + Counting Sort]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 방법 2와 크게 다른 건 없다.

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 입력의 범위는 1 ~ 1000이므로 1001개의 index를 둔다.
		int[] arr = new int[1001];

		// Counting Sort 
		while (N-- > 0) {
			arr[Integer.parseInt(st.nextToken())]++;
		}

		int prev = 0;	// 이전까지의 대기시간 누적합
		int sum = 0;	// 사람별 대기시간 총합
		
		for (int i = 0; i < 1001; i++) {
			
			// 해당 i index가 0이 될 때 까지 반복 
			while (arr[i]-- > 0) {
				// 이전까지의 대기시간과 현재 사람이 걸리는 시간을 더해준다.
				sum += (i + prev);
				
				// 이전까지의 누적합에 현재 걸리는 시간을 더해준다.
				prev += i;
			}
		}
		System.out.println(sum);
	}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 23087902  -  방법 3 : BufferedReader + Counting Sort

채점 번호 : 23087895  -  방법 2 : Scanner + Counting Sort

채점 번호 : 23087889  -  방법 1 : Scanner + Arrays.sort()

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

 

워낙 간단한 문제라 대체로 쉽게 풀었을 것이다. 정답 비율이 65%인 것 보면 확실히 쉬운 문제인 것 같다. 만약 입력받는 N이 더욱 큰 수가 들어왔다면 정렬에서 시간차이가 확연하게 발생했을텐데 N도 1 ~ 1000까지인지라 크게 차이는 안나는 것 같다.

 

만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.