[백준] 2108번 : 통계학 - JAVA [자바]
2108번: 통계학
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
www.acmicpc.net
- 문제
그리 어렵지 않은 문제지만 약간의 함정이 있으니 주의해야한다.
※ 주의할 점
- 동일한 최빈값이 있을경우 '두 번째로 작은 값'을 출력해야 한다.
- 알고리즘 [접근 방법]
기본적으로 이 문제를 풀기 위해서는 Counting Sort(카운팅 정렬)을 사용할 것이다. 물론 정렬을 쉽게 하기 위해 Arrays.sort 로 풀 수도 있지만 최빈값을 구하는 과정에 있어 '두 번째로 작은 값'을 출력해야하다보니 조금 복잡해진다. (사실상 중앙값 때문에 정렬을 해야하는 문제인데, 중앙값을 찾기 위해 직접 비교하면서 정렬을 하는 것은 비용소모가 크다.)
그래도 혹시 모르니 Arrays.sort 로 푸는 방법도 올리긴 하겠으나, 기본 토대는 카운팅 정렬을 사용할 것이다.
카운팅 정렬에 대한 자세한 내용은 아래 더보기의 두 링크를 참고하기 바란다.
카운팅 정렬 (Counting Sort / 계수 정렬) _ Java[자바]
Counting Sort [계수 정렬 / 카운팅 정렬] Counting Sort... 계수 정렬, 카운팅 정렬 등으로 많이 불리지만, 가장 와닿는 단어는 카운팅 정렬이므로 이 포스팅에서는 카운팅 정렬로 통일하여 쓰겠다. 카운�
st-lab.tistory.com
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다...
st-lab.tistory.com
Arrays.sort 를 사용한 방법은, 해당 메소드를 이용하여 정렬하게되면 중앙값은 (N+1) 위치의 값이 될 것이고, 범위는 0 번째 인덱스의 값과 (N-1) 번째 인덱스의 값의 차가 될 것이다.
최빈값이 문제인데, 배열 첫 번째 부터 탐색하여 각 값별 최빈값을 count 하면서 그중 가장 큰 빈도수 중, 두 번째로 작은 값을 찾아내야 한다. 즉, 플래그(flag) 변수를 하나 두고 빈도수가 같았던 적이 있는지 여부를 판별해야 한다.
자세한 내용은 코드에 주석으로 달아놓았으니 참고하시면 된다.
- 3가지 방법을 이용하여 풀이한다.
먼저 가장 기본적인 카운팅 정렬을 이용한 방법을 보여줄 것이다. 다만, 해당 풀이에 있어 입력방법을 달리하여 Scanner 와 BufferedReader 을 각각 사용할 것이다.
마지막으로 Arrays.sort로 풀고싶은 분들을 위해 해당 방법으로 사용한 코드를 보여주겠다. 대신 이 방법은 BufferedReader 로만 보여줄 것이니, Scanner 로 변경하고 싶으신 분은 입력 방법만 변경하여 제출하시면 된다.
- 풀이
- 방법 1
/*
counting 정렬을 사용한 방법
st-lab.tisotry.com
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
// 입력값의 범위 : -4000 ~ 4000
int[] arr = new int[8001];
/*
* sum = 총 합계
* max = 최댓값
* min = 최솟값
* median = 중앙값
* mode = 최빈값
*/
int sum = 0;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
// median 과 mode 는 -4000~4000 을 제외한 수로 초기화하면 된다.
int median = 10000;
int mode = 10000;
for(int i = 0; i < N; i++) {
int value = in.nextInt();
sum += value;
arr[value + 4000]++;
if(max < value) {
max = value;
}
if(min > value) {
min = value;
}
}
// 순회
int count = 0; // 중앙값 빈도 누적 수
int mode_max = 0; // 최빈값의 최댓값
// 이전의 동일한 최빈값이 1번만 등장했을경우 true, 아닐경우 false
boolean flag = false;
for(int i = min + 4000; i <= max + 4000; i++) {
if(arr[i] > 0) {
/*
* <중앙값 찾기>
* 누적횟수가 전체 전체 길이의 절반에 못 미친다면
*/
if(count < (N + 1) / 2) {
count += arr[i]; // i값의 빈도수를 count 에 누적
median = i - 4000;
}
/*
* <최빈값 찾기>
* 이전 최빈값보다 현재 값의 빈도수가 더 높을 경우
*/
if(mode_max < arr[i]) {
mode_max = arr[i];
mode = i - 4000;
flag = true; // 첫 등장이므로 true 로 변경
}
// 이전 최빈값 최댓값과 동일한 경우면서 한 번만 중복되는 경우
else if(mode_max == arr[i] && flag == true) {
mode = i - 4000;
flag = false;
}
}
}
System.out.println((int)Math.round((double)sum / N)); // 산술평균
System.out.println(median); // 중앙값
System.out.println(mode); // 최빈값
System.out.println(max - min); // 범위
}
}
가장 기본적인 방법이라 할 수 있겠다.
입력과 동시에 누적합은 바로바로 해주면서, 동시에 카운팅 정렬을 위한 배열의 index 값을 1 증가시킨다.
중요한 것은 최빈값인데, 만약에 이전의 최빈값의 최댓값보다 현재 최빈값이 더 클 경우, 즉 처음으로 나타난 최빈값일 경우 해당 index(i)를 최빈값에 초기화 해주며, flag 를 true 로 변경한다.
만약, 동일한 최빈값을 갖고있으면, 두 가지의 경우의 수가 생긴다. 첫 번째는 동일한 최빈값이 이전에 1 번만 나타났을경우인데, 이 경우에는 flag 가 true 일 테니 두 번째로 작은 값이 현재 i 가 되고 결과적으로 mode(최빈값 변수)를 초기화 해주면 된다. 그리고 반드시 flag를 false 로 바꿔주어야 된다. 이후에 같은 최빈값이 또 나오더라도 이미 두 번째로 작은 값은 변하지 않기 때문에 그래야 else if 문을 실행시키지 않으면서 두 번째로 작은 최빈값이 수정되지 않는다.
그리고 산술평균 출력의 경우 그냥 나누면 int 형 때문에 나눗셈 과정에서 무조건 소수점은 버려지기 때문에 반올림을 위해 Math.round를 쓰기 전에 이미 나눗셈에서 오차가 날 수 있다. 그러므로 sum 이나 N 둘 중 하나를 double 로 캐스팅하여 소수점이 버려지는 것을 방지하고, 반올림을 한 다음 int형으로 다시 캐스팅해야한다.
- 방법 2
위 알고리즘이랑 같고, 입력만 달리한 방법이다.
/*
counting 정렬을 사용한 방법
st-lab.tisotry.com
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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());
// 입력값의 범위 : -4000 ~ 4000
int[] arr = new int[8001];
/*
* sum = 총 합계
* max = 최댓값
* min = 최솟값
* median = 중앙값
* mode = 최빈값
*/
int sum = 0;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
// median 과 mode 는 -4000~4000 을 제외한 수로 초기화하면 된다.
int median = 10000;
int mode = 10000;
for(int i = 0; i < N; i++) {
int value = Integer.parseInt(br.readLine());
sum += value;
arr[value + 4000]++;
if(max < value) {
max = value;
}
if(min > value) {
min = value;
}
}
// 순회
int count = 0; // 중앙값 빈도 누적 수
int mode_max = 0; // 최빈값의 최댓값
// 이전의 동일한 최빈값이 1번만 등장했을경우 true, 아닐경우 false
boolean flag = false;
for(int i = min + 4000; i <= max + 4000; i++) {
if(arr[i] > 0) {
/*
* <중앙값 찾기>
* 누적횟수가 전체 전체 길이의 절반에 못 미친다면
*/
if(count < (N + 1) / 2) {
count += arr[i]; // i값의 빈도수를 count 에 누적
median = i - 4000;
}
/*
* <최빈값 찾기>
* 이전 최빈값보다 현재 값의 빈도수가 더 높을 경우
*/
if(mode_max < arr[i]) {
mode_max = arr[i];
mode = i - 4000;
flag = true; // 첫 등장이므로 true 로 변경
}
// 이전 최빈값 최댓값과 동일한 경우면서 한 번만 중복되는 경우
else if(mode_max == arr[i] && flag == true) {
mode = i - 4000;
flag = false;
}
}
}
System.out.println((int)Math.round((double)sum / N)); // 산술평균
System.out.println(median); // 중앙값
System.out.println(mode); // 최빈값
System.out.println(max - min); // 범위
}
}
크게 설명할 것이 없는 것 같다.
조언한다면 형 변환만 조심하자!
- 방법 3
Arrays.sort 를 사용하는 방법이다.
앞서 이미 말했지만 사실 중앙값을 구하기 위해 정렬을 하는 것인데, 카운팅 정렬은 시간복잡도가 O(N), Arrays.sort() 의 경우 평균 시간복잡도가 O(NlogN) 이므로 비용손실이 크다. 더군다나 결과적으로 counting 정렬의 경우 애초에 해당 값의 빈도수가 value 값으로 들어가있기에 value 값 중 가장 큰 값끼리만 비교하면 되지만, 아래 방법은 각 값 자체가 value 값이기 때문에 count 를 한 번 더 해주는 것이다. 결과적으로는 Counting 정렬 메커니즘을 사용하는 것이나 다름 없다.
즉, 정렬단계에서 이미 N*log(N) 만큼의 시간비용이 들었고, 최빈값 N만큼의 시간비용을 들이기 때문에 비효율적인 것은 맞다.
반면에 Counting 정렬의 경우 N 만큼의 시간비용이 들고, 최빈값에서 N 만큼의 시간비용을 들인다. NlogN 도 정렬알고리즘에서 빠른 것이지만 그럼에도 N 과 NlogN 은 천지차이다..
/*
Arrays.sort를 사용한 방법
st-lab.tisotry.com
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
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());
int[] arr = new int[N];
int sum = 0;
for(int i = 0; i < N; i++) {
int value = Integer.parseInt(br.readLine());
arr[i] = value;
sum += value;
}
Arrays.sort(arr);
boolean flag = false;
int mode_max = 0;
int mode = 10000;
for(int i = 0; i < N; i++) {
int jump = 0; // 동일한 수가 나온만큼 i 값 jump 시킬 변수
int count = 1;
int i_value = arr[i];
for(int j = i + 1; j < N; j++){
if(i_value != arr[j]) {
break;
}
count++;
jump++;
}
if(count > mode_max) {
mode_max = count;
mode = i_value;
flag = true;
}
else if(count == mode_max && flag == true) {
mode = i_value;
flag = false;
}
i += jump;
}
System.out.println((int)Math.round((double)sum / N));
System.out.println(arr[N / 2]); // index 는 0 부터 시작하므로 주의
System.out.println(mode);
System.out.println(arr[N - 1] - arr[0]);
}
}
- 성능
위에서 부터 순서대로
채점 번호 : 20141114 - 방법 3 : Arrays.sort + BufferedReader
채점 번호 : 20141108 - 방법 2 : 카운팅 정렬 + BufferedReader
채점 번호 : 20141103 - 방법 1 : 카운팅 정렬 + Scanner
입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.
그리고 같은 입력이더라도 Arrays.sort 를 쓰니까 대략 1.6배? 정도 느려진다. 이렇게 정렬 방법과 그에따른 시간 복잡도에 따라 시간차이가 날 수 있음을 볼 수 있다.
- 정리
이번 문제는 사실 어렵지는 않은 문제다. 그럼에도 정답률이 20%대인 이유가 이러한 함정들에 빠졌기 때문이 아닐까...
오늘 가장 중요한 점은 각 문제에 맞는 최적의 알고리즘을 찾고 적용하는 것이 아닐까 싶다.
참고로 필자가 테스트해본 결과 Arrays.sort 를 사용하면서 Scanner 를 사용하면 시간이 다음과 같이 걸린다.
'JAVA - 백준 [BAEK JOON] > 정렬' 카테고리의 다른 글
| [백준] 11650번 : 좌표 정렬하기 - JAVA [자바] (49) | 2020.06.10 |
|---|---|
| [백준] 1427번 : 소트인사이드 - JAVA [자바] (12) | 2020.06.03 |
| [백준] 10989번 : 수 정렬하기 3 - JAVA [자바] (22) | 2020.05.31 |
| [백준] 2751번 : 수 정렬하기 2 - JAVA [자바] (32) | 2020.05.30 |
| [백준] 2750번 : 수 정렬하기 - JAVA [자바] (14) | 2020.05.29 |