Do it! 코딩테스트-기초편. 3_자료구조2

오늘은 자료구조 편 문제 풀이 2번째 시간이다. 
https://www.acmicpc.net/problem/1546

1546번: 평균

문제를 읽어보고 시간 복잡도 -> 분석 -> 텍스트 코딩 -> 실제 코딩 순서로 진행해 보자 

1. 시간 복잡도 

해당 문제의 시간 제한은 2초이기 때문에 2억 번의 연산 안에 마무리하면 된다. 
문제에서 제시되는 데이터의 크기가 1000개 이하이기 때문에 일반적인 연산을 통해서도 시간제한 나오기는 쉽지 않을 것이다. 

2. 분석

최고점을 구한 후에 각 점수를 변환하고, 변환한 점수를 다시 더해서 평균을 구하는 간단한 문제이다. 
하지만 이 경우에도 연산 횟수를 줄여보도록 하자.
최악의 경우를 생각해서 연산 횟수를 계산해보면 일일이 비교해 보면서 최고점 구하기(1000), 점수 변환(1000), 변환 점수 모두 더하기(1000) 이렇게 하면 총 3000번의 연산이 이뤄진다. 
지난 시간에 설명한대로, 시간 복잡도는 O(3N)이지만 입력값이 무수히 커질수록 계수(3)는 충분히 무시할 수 있다고 했기 때문에 O(N)으로 생각해도 되겠지만, 실제 연산을 1000번으로 줄여볼 수 있을 것 같다. 

단순한 공식을 생각해보자. A, B 두 개의 수가 들어왔다고 가정하고, 최댓값이 M이라고 해보자. 공식은 아래와 같다.
( A / M * 100 + B / M * 100) / 2 = ( A / M + B / M) * 100 / 2 = ( A + B ) * 100 / M / 2
간단한 수학의 분배법칙을 이해하고 있다면 쉽게 이해할 수 있을 것이다. 

위의 공식을 일반화하면 아래와 같다.
( 입력값의 총합 ) * 100 / Max / N

결론적으로 반복문을 통해 값을 입력 받을 때, 최댓값과 총합을 구한다면 바로 답을 도출할 수 있다는 점이다.

3. 텍스트 코딩

1. 값의 개수를 입력받자. (Scanner or BufferedReader)
2. 점수를 입력받을 배열, 총합과 최댓값을 저장할 변수를 만들자. 1000개의 점수가 100점이라고 해도 int형 안에서 처리가 가능하지만 이왕이면 long형을 사용하는 습관을 들이자. 
3. 구한 최댓값과 총합을 사용해서 결론을 도출하자. 

4. 구현하기 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Stream;

public class Main  {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int [] array = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        long sum = 0;
        long max = 0;

        for(int i=0; i<N; i++){
            sum += array[i];
            max = max < array[i] ? array[i] : max;
        }

        System.out.println(sum * 100.0 / max / N);
    }
}