[BOJ] 백준 15954 인형들(카카오코드페스티벌)-java

문제

카카오프렌즈 스토어에서는 N종류의 인형을 팔고 있다. 

N개의 인형들 중에서는 잘 팔리는 인형과 그렇지 않은 인형들이 섞여 있어서 잘 팔리는 인형은 상대적으로 사람들이 많이 볼 수 있는

 곳에 배치하고, 잘 팔리지 않는 인형은 상대적으로 사람들이 적게 볼 수 있는 곳에 배치한다. 그러므로 배치된 곳이 가까운 두 인형은

 상대적으로 판매량이 비슷하다고 할 수 있다. 좋은 배치를 정하기 위해서 어느 날, 여러 명의 사람들을 대상으로 인형의 선호도를 조

사하였다. 조사 결과 각 인형에 대해서 선호하는 사람의 수를 모두 구하였고, 그에 따라 인형의 배치를 정하려고 한다.

카카오프렌즈 스토어를 관리하는 브라이언은 어떠한 특정한 곳에 인형들을 배치하고자 하는데, 그곳에 인형들을 선택하는 방법은 다음과 같다:

• 먼저 비슷한 인형이 가깝게 위치하도록 서로 다른 N개의 인형을 종류당 한 개씩 일렬로 배치한다.
• 그 후, 선호하는 사람의 수의 표준편차가 최소가 되는, K개 이상의 연속된 위치에 있는 인형들을 선택하여 그들을 같은 곳에 배치한다.

위의 방법으로 인형들을 선택했을 때, 선택된 인형들의 선호하는 사람의 수의 표준편차를 구하여라.

N개의 수 a1, a2, …, aN이 주어져 있을 때, 통계학에서 (산술) 평균은 (a1 + a2 + … + aN) / N 으로 정의한다. 이를 m으로 정의하자.

 또한, 분산은 ((a1 - m)2 + (a2 - m)2 + … + (aN - m)2) / N으로 정의하고, 표준 편차는 분산의 음이 아닌 제곱근으로 정의한다.

입력

첫 번째 줄에 N과 K가 주어진다. N은 1 이상 500 이하의 정수이고, K는 1 이상 N 이하의 정수이다.

두 번째 줄에는 N개의 정수가 입력되며, 이는 인형이 일렬로 나열된 순서대로 인형을 선호하는 사람의 수이다. 

각 수는 모두 106 이하의 음이 아닌 정수이다.

출력

선택된 인형들을 선호하는 사람의 수의 표준 편차를 출력한다. 출력한 결과와 실제 답을 비교하였을 때의 상대/절대 오차가 10-6 이하

인 경우에만 정답으로 인정한다.

문제:https://www.acmicpc.net/problem/15954

import java.io.*;
import java.util.*;
 
public class doll {
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); 
        int k = Integer.parseInt(st.nextToken());
        int[] arr = new int[n]; // 인형을 선호하는 사람의 수를 저장할 배열
        double variance = 0, tmp = 0, average = 0, stdDeviation = 0; // 분산,평균,표준편차
        double min = 10000000; 
 
        st = new StringTokenizer(br.readLine()); 
        for (int i = 0; i < n; i++) { 
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i <= n - k; i++) {
            int count = k; // k개 이상이기때문에 k개부터 하나씩 늘려가면서 표준편차가 최소일 때를 찾아야 함
            while (i + count <= n) { // 배열의 끝까지 연속할 경우를 확인해야하므로 i+count가 n보다 작거나 같을때까지만 반복
                tmp = average = variance = stdDeviation = 0; //
                for (int j = 0; j < count; j++) {
                    tmp += arr[i + j]; 
                }
                average = tmp / count; // 평균 구하기
                tmp = 0;
                for (int j = 0; j < count; j++) { // 분산구하기
                    tmp += (arr[i + j] - average) * (arr[i + j] - average); 
                }
                variance = tmp / count; // 분산 구하기
                stdDeviation = Math.sqrt(variance); // 표준 편차 구하는 함수
                min = Math.min(min, stdDeviation); 
                count++;
            }
        }
        System.out.println(String.format("%.12f", min)); 0
 
    }
 
}
 

풀이

이 문제는 n과 k가 주어졌을 때 n개의 인형에 대학 각각의 선호도를 데이터로 입력받고 그 선호도에 대해서 적어도 k개 이상 연속하는 데이터중에 표준편차가 최소일 때를 찾아야 하는 문제입니다. k개로 고정이 되었다면 처음부터 한개씩 뒤로 이동하면서 연속하는 부분집합을 구해서 비교하면 간단했겠지만 k개 이상이므로 첫번째 데이터부터 연속할 때 k개,k+1개,k+2개,..,n개 이런식으로 항상 확인 한 후 두번째 데이터 부터 k개,k+1개... 이렇게 확인하는 문제입니다.