개발자 톡
연습문제 톡
[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회_정기_코딩_인증평가_기출]_자동차_테스트