[BOJ] 1206 사람의 수 - JAVA

1. 문제

1206번: 사람의 수

송유진은 길거리에서 사람들에게 설문조사를 하고 있다. 설문조사에는 N개의 문항이 있고, 설문에 응한 사람은 각 문항을 0보다 크거나 같고, 10보다 작거나 같은 정수로 대답해야 한다.
설문조사를 모두 마친 후 유진이는 각 문항의 평균 점수 소수점 셋째 자리에서 자른 값을 보고서 종이에 적고 사무실로 돌아왔다. 예를 들어, 어떤 문항에 각 사람이 점수를 4, 6, 10점으로 대답했다면, 평균 점수는 6.666이다. 이제 설문조사 결과를 보고해야 하는데, 문제가 하나 생겼다. 평균 점수만 알고 있기 때문에, 설문조사에 참여한 사람의 수를 알 수 없다는 점이다.
각 문항의 평균 점수가 주어진다. 이때 설문조사에 참여한 사람의 수를 구해보자.

---

2. 풀이

double 풀이

1.  입력값에서 소수점 부분만 남긴다. (주석 단 코드처럼 하면 부동소수점 오차때문에 틀린다.)

2.  num=사람 수다. 명수를 올려가면서 탐색한다.

2-1.  cases에 점수를 사람 수로 나눈 값을 저장한다. 점수의 범위는 1점부터 사람 수까지로 한다. 입력값을 소수점부분만 받았기 때문에 그 이상은 의미가 없기 때문이다.

2-2.  N개의 입력값을 하나하나 binarySearch로 찾는다. 이 때, 나는 cases 배열을 1001칸으로 고정했으므로 범위를 지정해야 한다. 0부터 num+1까지로 한다. fromIdx는 포함, toIdx는 제외라서 num+1이어야 한다.

2-3.  만약 입력값이 cases에 없다면 flag를 false로 변경하고 반복문을 중단한다.

2-4.  반복문이 끝난 뒤에도 flag가 true라면 정답을 찾은 것이므로 num(사람수)를 출력하고 끝낸다.

import java.io.*;
import java.util.*;

public class BOJ_1206_사람의수 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      double[] avg = new double[N];

      for (int i = 0; i < N; i++) {
//       avg[i] = 0.001 * Integer.parseInt(in.readLine().split("\\.")[1]);
         avg[i] = Double.parseDouble(in.readLine());
         avg[i] = avg[i] - Math.floor(avg[i]);
         avg[i] = Math.round(avg[i]*1000.0)/1000.0;
      }


      boolean flag;
      double[] cases = new double[1001];
      for (int num = 1; num <= 1000; num++) {
         for(int score=1;score<=num;score++){
            cases[score] = Math.floor(((double)score/num)*1000)/1000.0;
         }
         flag = true;
         for(int j=0;j<N;j++){
            if(Arrays.binarySearch(cases, 0, num+1, avg[j]) <0){
               flag = false;
               break;
            }
         }
         if(flag){
            System.out.println(num);
            return;
         }
      }
   }

}

 

BigDecimal 풀이

부동소수점때문에 너무 힘들어서 BigDecimal 타입을 써봤다.

1.  입력값을 .으로 구분한 뒤 [1]칸값 앞에 "0."을 붙인다. 이걸 BigDecimal로 만든다.

2.  방식은 위와 흡사하다. 하지만 나누기를 할 때(19번째 줄) 3번째 자리까지, 그 외의 자리는 버린다(RoundingMode.DOWN) 고 설정한 점이 다르다.

3.  double 풀이에서는 점수가 0일때 어차피 항상 0이라서 굳이 계산하지 않고 score를 1부터 시작했는데, BigDecimal은 객체이므로 꼭 계산해줘야 한다.

import java.io.*;
import java.math.*;
import java.util.*;

public class BOJ_1206_사람의수2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      BigDecimal[] avg = new BigDecimal[N];

      for (int i = 0; i < N; i++) {
         avg[i] = new BigDecimal("0."+in.readLine().split("\\.")[1]);
      }

      boolean flag;
      BigDecimal[] cases = new BigDecimal[1001];
      for (int num = 1; num <= 1000; num++) {
         for(int score=0;score<=num;score++){
            cases[score] = BigDecimal.valueOf(score).divide(BigDecimal.valueOf(num),3, RoundingMode.DOWN);
         }
         flag = true;
         for(int j=0;j<N;j++){
            if(Arrays.binarySearch(cases, 0, num+1, avg[j]) <0){
               flag = false;
               break;
            }
         }
         if(flag){
            System.out.println(num);
            return;
         }
      }

   }

}

---

3. 결과

소수점때문에 너무너무너무 힘들었다..

맨 위의 코드는 BigDecimal을 이용한 코드다. 메모리도 시간도 훨씬 더 많이 걸린다. 새 객체를 계속 생성해서 그런 것 같다.