소프티어

시간복잡도 O(NlogN)~=O(Q) : 제일 빠른 풀이 (답 주의)

문제의 특성은 데이터가 너무 크다는 것이고 O(NQ)만 되도 벌써 시간초과가 뜰 것입니다. 다만 여기서 큰 힌트 2가지를 통해 시간복잡도를 선형으로 대폭 줄일 수 있습니다. 중앙값을 구할 수 있는 경우의 수만 찾으면 됨 주어지는 자동차의 연비는 서로 다름을 가정해도 좋습니다. 1번 조건은 말 그대로입니다. 중앙값이란 [1,2,3,5,8] 데이터에서도 3 [1,2,3,100,288] 데이터에서도 3입니다. 쉽게 설명하자면 인덱스만 알면 나머지 데이터가 어떻게 생겼든 상관이 없습니다. 저희는 3이 될 수 있는 조합만 찾으면 되는데 3대만 뽑는다는 건 어떻게 뽑아도 [(O), M, (O)] 가 되게끔만 해주는 "경우의 수"만 찾으면 됩니다. 그렇다면 정렬을 해놓고 (median 이전에 나오는 숫자의 개수 x 이후에 나오는 숫자의 개수) 로 그 조합을 찾을 수 잇습니다. 2번 조건은 1번 조건을 위한, 더 빨리 풀 수 있도록 하는 힌트입니다. 서로 다름을 가정 = 각 숫자마다 inde...

간단히 만들어본 테스트케이스 모음입니다.

``` 1) 최소 1 1 1 1 -> 0 2) 3개 못뽑음1 2 1 1 2 1 -> 0 3) 3개 못뽑음2 2 1 1000000000 1 1 -> 0 4) 연비 조절해보기 3 4 1000000000 1 500000000 1000000000 1 500000000 500000001 -> 0 0 1 0 ```

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

문제는 다음과 같이 풀었는데 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.re...

파이썬 split(), split(" ") 문제

다른 코드는 다 똑같은 상태에서 n, q = map(int, input().split()) ratio = list(map(int, input().split())) -> split(" ") 로 변경하면 런타임 에러가 뜹니다. 아마 입력 문제인 거 같습니다. 두 개의 차이점은 아래와 같습니다. split() -> 공백(" "), 개행("\n"), 탭("\t")을 기준으로 나눔 split(" ") -> 공백(" ")을 기준으로 나눔 입력 중 n이 매우 큰 경우에 런타임 에러가 생기는 거 같은데 혹시 왜 그런지 이유를 아시는 분 있을까요?

JavaScript 채점이 정말 맞는건지 궁금합니다.

let inputs = require("fs")   .readFileSync("/dev/stdin")   .toString()   .trim()   .split("\n"); let [n, q] = inputs[0].split(" ").map(Number); let arr = inputs[1].split(" ").map(Number); arr.sort((a, b) => a - b); for (let i = 0; i < q; i++) {   let m = Number(inputs[2 + i]);   let lo = -1;   let hi = n - 1;   while (lo + 1 < hi) {     let mid = Math.floor((lo + hi) / 2);     if (arr[mid] >= m) {       hi = mid;     } else {       lo = mid;     }   ...

뭐가 틀린건지 모르겟네요..

import java.io.*; import java.util.*; public class Main {   public static void main(String[] args) throws IOException {     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     StringTokenizer st = new StringTokenizer(br.readLine());     int n = Integer.parseInt(st.nextToken());     int q = Integer.parseInt(st.nextToken());           st = new StringTokenizer(br.readLine());           ArrayList<Integer> list = new ArrayList<...

시간초과 문제 질문드립니다.

아래 코드에서 시간초과를 해결하지 못한 거 같은데 어디를 수정하면 좋을까요? input = sys.stdin.readline n,q = map(int,input().split()) data = list(map(int,input().split())) data.sort() for _ in range(q):   num = int(input())   start = 0   end = n-1   left = 0   right = 0   ans = 0   while start <= end:     if start == end:       if data[start] == num:         ans = left * right       break     if data[start] < num:       left += 1       start += 1     if data[end] > num:       right += 1       end...

자동차 테스트 시간초과 문제 JAVA

JAVA로 해당 문제 테스트 통과하고 제출해서 시간초과가 뜨길래 이중 for문 지우고 while로 했는데도 해당 문제가 발생하네요. 혹시 어느 부분 수정하면 되는지 알려주실 수 있을까요? 감사드립니다. import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException // 예외 처리 { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 버퍼 리더 StringTokenizer st = new StringTokenizer(br.readLine()); // 스트링 토큰화 int n = Integer.parseInt(st.nextToken()); // n개의 자동차 ...

[HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트 시간초과 질문드립니다.

import sys from collections import defaultdict N, M = map(int, sys.stdin.readline().split()) dic = defaultdict(int) arr = list(map(int, sys.stdin.readline().split())) arr.sort() for i in range(len(arr)): dic[arr[i]] = i * (len(arr)-i-1) for _ in range(M): num = int(sys.stdin.readline()) if num < arr[0] or num > arr[-1]: print(0) else: print(dic[num]) 제가 풀이한 코드입니다. 이번 HSAT에서 틀렸으면 이 문제에서 틀렸을꺼 같은데 시간초과날 부분이 있을까요? 연습문제에서는 통과했습니다.