글 읽기 - 시간 초과 질문

lsnfamily02 6년 전 0

코드는 다음과 같습니다

먼저 리스트를 두개로 쪼개고

각 리스트에서 최대의 갯수를 갖는 색깔을 찾습니다. (왼쪽에서 하나 오른쪽에서 하나)

그리고 쪼갠 리스트를 다시 합쳐서, 아까 찾은 두개의 후보군 중에서

합친 리스트의 갯수 절반을 넘는 색깔을 찾습니다

시간 복잡도는 2*T(n/2) + O(n)

이라 nlogn이 나오는데.. 어디서 잘못된걸까요?

​

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
// colorNum ranges [1, 10,000]
public static int find(int start, int end) {

if(start == end){
return dwarfs[start];
}

int middle = (start + end) / 2;
int leftColor = find( start, middle);
int rightColor = find(middle + 1, end);
int count = 0;
int threshold  = (end- start +1)/2 ;
if (leftColor == rightColor)
return leftColor;
for (int i = start; i <= end; i++) {
if (leftColor == -1)
break;
int color = dwarfs[i];
if (leftColor == color)
count++;
}
if (count > threshold)
return leftColor;
count = 0;
for (int i = start; i <= end; i++) {
if (rightColor == -1)
break;
int color = dwarfs[i];
if (rightColor == color)
count++;
}
if (count > threshold)
return rightColor;
else
return -1;

}
static int colorNum;
static int[] dwarfs;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
colorNum = Integer.parseInt(st.nextToken());
dwarfs = new int[N + 1];
int[] ans;
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i < N + 1; i++) {
dwarfs[i] = Integer.parseInt(st.nextToken());
}

int M = Integer.parseInt(br.readLine());
ans = new int[M+1];

for (int i = 0; i < M; i++) {
String[] tokens = br.readLine().trim().split(" ");
int s = Integer.parseInt(tokens[0]);
int t = Integer.parseInt(tokens[1]);
int color = find(s, t);
ans[i] = color;
}
StringBuffer sb = new StringBuffer();
for(int a : ans){
if(a == -1) {
sb.append("no\n");
}
else {
sb.append("yes "+a+"\n");
}
}
System.out.println(sb.toString());

}

}

sgchoi5 6년 전 0

COCI 문제는 대회에서 사용했었던 TC (Judge Data) 가 공개되어 있습니다.

그거 잘 되는지 우선 해보세요.

http://gooddaytocode.blogspot....

ntopia 6년 전 0

nlogn 연산을 총 m번 반복하니까 시간초과겠죠

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

문제

문제

출처

ICPC

시간 초과 질문

lsnfamily02 6년 전 0

sgchoi5 6년 전 0

ntopia 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말