글 읽기 - java, 통계학 시간초과

cirly 6년 전 0

알고리즘 2108번 통계학 문제 입니다.

첫번째(mean), 두번째 (median), 세번째 (mode), 네번째 (범위) 구하는 문제 입니다.

세번째에서 그냥 처음에 list 로 돌렸다가 search O(n)로 시간초과가 떠서 list 대신 hashmap으로 바꿨습니다.

하지만 mode의 count 가 중복되는 경우 2번째로 작은 숫자를 print하라고 하는 부분에서 막혀 질문을 드립니다.

Hashmap으로 approach 하다보니 maxcount가 중복되는 key를 찾을 수도 없고, hashmap을 swap해서 하려고 했지만

복잡해서 그만뒀습니다.

다른 approach가 있는지 궁굼합니다.

import java.util.*;

//import java.util.stream.Collectors;

public class algorithm_2108 {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    // number of ints stored in 'n'
    int n = sc.nextInt();

    //list array
    List<Integer> list_result = new ArrayList<Integer>();

    //if sc has next int in line
    if (sc.hasNextInt()){
      for (int i = 0; i < n; i++) {
        //store them into a list
        list_result.add(sc.nextInt());
        //System.out.println(list_result) - debug;
      }
    }

    //1 method
    System.out.println(list_average(list_result));

    //2 method
    Collections.sort(list_result);
    System.out.println(middle_element(list_result));

    //3 method
    System.out.println(count_element(list_result));

    //4 method
    System.out.println(list_result.get(list_result.size()-1) - list_result.get(0));
  }

    // First method: sum of list numbers and divided by the length of the list(mean)
    public static int list_average(List<Integer> array){
      int average_sum = 0;
      for (int i = 0; i < array.size(); i++){
        average_sum = average_sum + array.get(i);
      }
      average_sum = (average_sum / array.size());
      return average_sum;
    }

    // Second Method: find the middle element's value(median)
    public static int middle_element(List<Integer> array){
      int median = 0;
      median = array.get((array.size()/2));
      return median;
    }

    //Third method to cacluate the mode
    public static int count_element(List<Integer> array){
      int count = 0; int maxCount = 0; int result = 0;
      HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>();
      for (int i = 0; i < array.size(); i++){
        if (hs.get(array.get(i)) != null){
          count = hs.get(array.get(i));
          count = count + 1;
          hs.put(array.get(i), count);

          if (count > maxCount){
            maxCount = count;
            result = array.get(i);
          }
        } else {
          hs.put(array.get(i), 1);
        }
      }
      /*Map<Integer, Integer> map = new HashMap<>();
      Map<Integer, Integer> swapped = hs.entrySet().stream().collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));
      if (swapped.get(maxCount) == maxCountZA
      }*/
      return result;
    }
}

djm03178 6년 전 0

정렬을 해서 순서대로 확인하면, 정렬하는 데에 O(n lg n), 전체를 확인하는 데에는 O(n)으로 가능합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

java, 통계학 시간초과

cirly 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말