개발자 톡

연습문제 톡 [HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트

[Java 시간초과] TreeSet으로 작은원소집합개수 * 큰원소집합개수 를 사용해 풀었는데 시간초과가 왜 나는지 모르겠어요

등록일
2024-09-03 11:47:15
조회수
207
작성자
hyeseon97

문제는 다음과 같이 풀었는데

3.06~3.07초로 시간초과가 납니다

시간복잡도 계산을 Q * 2logN 로 하면 이백만도 안되는데 안나오는데 왜 시간초과가 나는지 모르겠습니다


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


public class Main {


    // 차량 수
    static int N;
    // 질의 수
    static int Q;
    // 차량 연비를 기준으로 정렬 저장
    static TreeSet<Long> sorted;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        sorted = new TreeSet<>();


        st = new StringTokenizer(br.readLine());
        for(int i = 0;i<N;i++){
            sorted.add(Long.parseLong(st.nextToken()));
        }


        // 질의별 해당 연비가 중앙값이 되는 경우 계산
        // 해당 연비보다 작은 연비들 * 큰 연비들 이 중앙값이 되는 경우
        // 단 해당 연비가 set에 존재하지 않으면 경우의 수는 0인거 고려
        // 결과 저장
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<Q;i++){
            long q = Long.parseLong(br.readLine());


            if(!sorted.contains(q)) {
                sb.append("0\n");
                continue;
            }
            
            int small = sorted.headSet(q).size(); // headSet()은 해당원소보다 작은 원소의 부분집합 반환
            int big = sorted.tailSet(q).size()-1; // tailSet()은 해당원소를 포함하면서 큰 원소의 부분집합 반환
            sb.append(small * big + "\n");
        }


        System.out.println(sb.toString());


        
    }
}



#[HSAT_7회_정기_코딩_인증평가_기출]_자동차_테스트

이 카테고리의 톡 더보기