문제 url:
통계학
문제:
🤔 문제 알아보기
사실 문제자체는 이해하기 쉬운 문제이다. 특별한 설명이 필요없으며,
시간 제한도 2초라서, N이 500,000개 까지 가능할 때, O(N ^2) 미만 즉,
O(N log N)까지 운이 좋으면 가능할 수 있다.
※빅오 표기법은 최악 즉, 상한선을 기준으로 하는데, 만약 O(N log N)의 상한선까지 채운다면!, 이것도 안좋은 방법일 수 있다.
그래서, 최대한 시간 복잡도가 효율적인 것을 찾아야 한다.
마지막으로, 해당 문제의 함정이 존재한다면 최빈값이 여러 개 존재할 때, 최빈값 중 2번째로 작은 값을 출력하라는 점이 존재한다. 이 점을 유의해서 풀어야 한다.
필자가 생각한 것은 여기까지다.
하지만, 문제를 결국 풀지 못하였다. 아무래도 아직까지 구현에 약한 모습들이..그래서 타 블로그에서 설명한 코드를 이해한 후 여기에 기록하고자 한다.
코드를 확인하고 싶은분은 아래 링크를 확인해 주시는 것이 더 좋다.
[백준] 2108번 : 통계학 - JAVA [자바] Stranger's LAB
필자는 블로그에서 했던 방식 그대로, 계수 정렬(counting sort)와 Arrays.sort()메서드를 활용한 풀이 둘 다 해보았다.
이를 풀었던 코드를 살펴보자
🐱👤 실제 코드(계수 정렬 사용)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] counting_sort = new int[8001];
int sum = 0;
/*
* 최고값, 최소값을 구하기 위한 변수
* ↘ 입력받는 변수는 -4000 ~ 4000 이므로, 나올 수 없는 10000을 입력
* 중앙값을 구하기 위한 변수
* 최빈값을 구하기 위한 변수
* ↘ 중앙값, 최빈값 변수 모두 입력받는 변수는 -4000 ~ 4000 이므로,
* 나올 수 없는 10000을 입력
*/
int max = -10000;
int min = 10000;
int median = 10000;
int freq = 10000;
for(int i = 0; i < N; i++) {
int value = Integer.parseInt(br.readLine());
// 추후 산술평균 구할 때 쓰기 위한 합계
sum+= value;
/*
* 해당 자리 숫자에 개수를 카운팅(빈도수 측정도 가능)
* 4000을 더한 이유는, 4000인덱스가 곧 0의 숫자값을 가지는 인덱스라서
*/
counting_sort[value+4000]++;
/*
* 추후 범위를 구할 때 사용
*/
if(value > max) {
max = value;
}
if(value < min) {
min = value;
}
}
/*
* 중앙값의 인덱스를 구하기 위한 변수
* 즉, 길이가 5인 배열이 존재한다고 보자,
* 그러면 인덱스가 2가 중앙값이 될 것인데
* 해당 문제는, 중복값들도 들어가기 때문에
* 이렇게 놔둔 것
*/
int count = 0;
/*
* 최대 빈도수를 구하는 변수
*/
int freq_max = 0;
/*
* 최대 빈도수 중복을 확인하기 위한 변수
* false라면 현재 최대 빈도수가 안나온 상태
* true면 최대 빈도수가 이미 나온 상태로 이걸 통해 중복된 빈도수를 제어할 수 있음
*/
boolean is_freq_rep = false;
/*
* 여기서 min+4000부터 시작하는 이유가
* 가장 작은 값의 counting_sort 배열부터 살펴볼거기 때문
* 그렇게 하면, 0부터 ~ 8000까지 하는 것보다 반복문이 줄어듦
*/
for(int i = min+4000; i < max+4001; i++) {
/*
* 한번이라도, 입력된 값이라면 0보다 클 것
* 즉, 현재 입력된 값들만 살펴본다는 의미이다.
*/
if(counting_sort[i] > 0) {
/*
* 중앙값 확인하기.
* 그럼 왜? (N+1) / 2를??
* 1 1 2 2 2 3 3 이 존재할 때, 여기서 중앙값은 2이다.
* 즉, (길이 7 + 1) / 2 => 4, 인덱스 4보다 작은 수까지 계산을 해야 한다는 것,
*/
if(count < (N+1) / 2) {
count += counting_sort[i];
/*
* 위에서 설명했듯, 4000은 0의 숫자를 의미하기 때문에
* 4000을 기준으로 음수와 양수를 표현할 수 있음
*/
median = i-4000;
}
if(freq_max < counting_sort[i]) {
freq_max = counting_sort[i];
freq = i-4000;
is_freq_rep = true;
}
/*
* 현재 중복된 최대 빈도수가 등장함.
*/
else if(freq_max == counting_sort[i] && is_freq_rep == true) {
freq = i - 4000;
/*
* false로 주는 이유는??
* 중복된 최대 빈도수 값이 나오면 우리는 조건에서 2번째로 작은 최대 빈도값을 구하기로 하였다.
* 그렇게 구하기 위해 해당 조건문에 못들어오도록 변수에 false를 주는 것,
*/
is_freq_rep = false;
}
}
}
// 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
System.out.println((int)Math.round((double)sum / N));
// 중앙값을 출력한다.
System.out.println(median);
//최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
System.out.println(freq);
// 범위를 출력한다.
System.out.println(max - min);
}
}
여기서 필자가 이해하는 데 시간이 걸렸던 코드 위주로 살펴보겠다.
(나머지는 주석으로 대체할 수 있다고 판단하여 하지 않겠다)
계수정렬에 대한 특징과 구현은 특별히 설명하지 않겠다.
만약 잘 모르는 분이 계신다면, 어떤 원리로 동작하는지 아래 링크를 통해 간략히 확인하고 오면 될 것이다.
[정렬] 계수 정렬(counting sort)에 대해 알아보자
1. 중앙값 확인하기
if(count < (N+1) / 2) {
count += counting_sort[i];
/*
* 위에서 설명했듯, 4000은 0의 숫자를 의미하기 때문에
* 4000을 기준으로 음수와 양수를 표현할 수 있음
*/
median = i-4000;
}해당 코드를 이해한 바를 설명하자면,
우리가 길이가 7인 배열에 1, 1, 1, 2, 2, 2, 3 값이 들어가 있다고 생각하자,
※ 문제 조건에서 길이 N이 홀수만 입력된다고 했다. 그래서 홀수만 보는 것이다.
우리 눈으로 쉽게 중앙값이 2인 것을 알 수 있다. 또 공식으로 풀자면 이럴 것이다.
배열의 길이 / 2 -> 7 / 2 = 3 그래서 인덱스 3의 값인 2를 구할 수 있다.
자, 이제 코드로 다시 넘어가면 count는 입력값 i가 몇번 중복되었는지를 세는 변수이다.
그런 값(count)가 (7 + 1) / 2 -> 4보다 작을때 count를 누적합을 해주며
median값을 계속 업데이트 해주는 것을 볼 수 있다.
그럼 카운트가 해당 중앙 인덱스보다 커지면, 로직이 돌아가지 않기 때문에
결국 마지막에는 중앙값이 median 변수에 들어가 있을 것이다.
2. 최빈값 확인하기
if(freq_max < counting_sort[i]) {
freq_max = counting_sort[i];
freq = i-4000;
is_freq_rep = true;
}
/*
* 현재 중복된 최대 빈도수가 등장함.
*/
else if(freq_max == counting_sort[i] && is_freq_rep == true) {
freq = i - 4000;
/*
* false로 주는 이유는??
* 중복된 최대 빈도수 값이 나오면
* 우리는 조건에서 2번째로 작은 최대 빈도값을 구하기로 하였다.
* 그렇게 구하기 위해 해당 조건문에 못들어오도록 변수에 false를 주는 것,
*/
is_freq_rep = false;
}위의 조건부터 확인해보면, 계수정렬도 세어진 갯수가 최대 빈도값(freq_max)보다 크다면 최빈값이기 때문에 개수와 해당 배열 값을 초기화 해준다.
또한 is_freq_rep 변수를 true로 해주는데,
해당 변수는 최대 빈도값이 여러 개 존재할 때, 2번 째로 작은 최대 빈도값을 구하기 위한 flag 변수로, else if문에서 사용된다.
그럼 else if문을 확인해보면,
freq_max가 현재 값의 개수와 일치하다면! (즉, 최대 빈도값이 여러 개가 존재함을 의미) 그러면서, is_freq_rep이 true라면,
최대 빈도값에 현재 빈도값을 저장한다.
즉, 예시로 현재 1이 3번나와서 freq_max가 3인 상태에서 2가 3번이 나온다면? 서로 빈도값이 같은 상황을 말한다.
여기서 잠깐 혼란이 와서 물어볼 수 있는 내용으로 왜 is_freq_rep이 true일 때 2번째로 작은 최빈값이 되는가?
그것은 이미 freq_max < counting_sort[i] 조건에서 true로 초기화 시켜주기 때문에
만약 3번째, 4번째 최빈값이 등장해도, 때려죽어도 해당 조건에 들어가지 못한다.
또한 else if문 역시 해당 조건을 만족하려면 is_freq_rep이 true여야 하기 때문에 3번째, 4번째는 무조건 false값으로 때려 죽어도 성립할 수 없기 때문에
2번째로 작은 최빈값만 저장될 수 있는 것이다.
🐱👤 실제 코드(Arrays.sort() 활용)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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];
// 산술 평균 구할 때 사용하기 위한, N개의 누적합 변수
int sum = 0;
// 값의 범위를 구하기 위한 min max 변수
// max - min을 통해 범위를 구할 수 있다.
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
// 중앙값과 최다 빈도값을 담는 변수
int median = 10000;
int freq_value = 10000;
for(int i = 0; i < N; i++) {
int value = Integer.parseInt(br.readLine());
sum += value;
arr[i] = value;
if(value > max) {
max = value;
}
if(value < min) {
min = value;
}
}
Arrays.sort(arr);
int freq_max = 0;
boolean is_freq_rep = false;
for(int i = 0; i < N; i++) {
int cnt = 1;
int jump = 0;
for(int j = i + 1; j < N; j++) {
// 다르면 더 이상 중복되는 값이 아니라는 의미
if(arr[i] != arr[j]) {
break;
}
jump++;
cnt++;
}
if(cnt > freq_max) {
freq_max = cnt;
freq_value = arr[i];
is_freq_rep = true;
}
else if(cnt == freq_max && is_freq_rep == true) {
freq_value = arr[i];
is_freq_rep = false;
}
i += jump;
}
System.out.println((int)Math.round((double) sum / N));
System.out.println(arr[(N-1) / 2]);
System.out.println(freq_value);
System.out.println(max - min);
}
}
사실 해당코드도 계수 정렬 코드와 비슷하기 때문에 위 코드를 보면 쉽게 이해할 수 있다.
그렇지만! 조금 다른 점이 존재하는데,
계수정렬과 다른 부분
for(int i = 0; i < N; i++) {
int cnt = 1;
int jump = 0;
for(int j = i + 1; j < N; j++) {
// 다르면 더 이상 중복되는 값이 아니라는 의미
if(arr[i] != arr[j]) {
break;
}
jump++;
cnt++;
}이 부분이 조금 다른데,
아래 for문(변수 j를 가지는)는 현재 i번째 값과 비교해서 같은지를 묻는 반복문이다.
그래서 같으면 중복개수(cnt 변수)를 1씩 증가하고,
j가 중복된 값 개수만큼 i 인덱스 값을 움직인 것이기 때문에
jump(추후 i에 누적합으로 더할 때 사용하는데, 인덱스를 움직인 횟수를 담는 변수이다)변수를 통해 현재 값과 일치하지 않는 인덱스 번호로 이동할 수 있다.
🤢 회고
해당 문제를 이해할 때는 그렇게 어렵지 않다고 생각했다.
하지만, 실제로 구현하려고 했을 때는 머리가 아프고 잘 풀리지도 않았다.
계속해서 코드로 접근하려는 사고방식이 구현을 망치고 있는 거 같은데,
앞으로는 노트에 먼저 손 코딩을 한 후 들어가는 연습을 해서
문제 로직과 필요한 자료구조를 파악한 다음 코드를 작성하도록 해보겠다.
알고리즘... 걱정이 많다...
아래는 필자가 틀린 코드이다. 기록을 위해 남겨놓겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
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];
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
System.out.println(avg(arr));
System.out.println(midValue(arr));
System.out.println(frequency(arr));
System.out.println(range(arr));
}
static long avg(int[] arr) {
double sum = 0;
for(int i = 0; i < arr.length; i++) {
sum += arr[i];
}
double res = sum / arr.length;
return Math.round(res >= 0 ? res: -res);
}
static int midValue(int[] arr) {
Set<Integer> set = new HashSet<>();
for(int i = 0; i < arr.length; i++) {
set.add(arr[i]);
}
Object[] removeRemoveArr = set.toArray();
Arrays.sort(removeRemoveArr);
return (int) removeRemoveArr[(arr.length-1) / 2];
}
static int frequency(int[] arr) {
int answer = arr[0];
int max = 1;
int[] freq = new int[8001];
int min_of_2 = 0;
for(int i = 0; i < arr.length; i++) {
if(arr[0] < arr[i]) {
min_of_2 = arr[i];
break;
}
}
for(int i = 0; i < arr.length; i++) {
freq[arr[i] + 4000]++;
if(max < freq[arr[i]+4000]) {
max = freq[arr[i]+4000];
answer = arr[i];
}
}
// 최빈값이 여러개 일 경우
int temp = 0;
for(int j = 0; j < 8001; j++) {
if(max == freq[j]) {
temp++;
}
if(temp > 0) {
answer = min_of_2;
break;
}
}
return answer;
}
static int range(int[] arr) {
if(arr.length == 1) {
return Math.abs(arr[0]);
}
int res = arr[arr.length - 1] + Math.abs(arr[0]);
return Math.abs(res);
}
}
