글 읽기 - Java 시간초과 질문입니다.

jrhopefulp 1년 전 0

대략 65퍼에서 시간초과가 나오는데 어떻게 해결해야 할지를 모르겠네요.

(1) binary search 한다음에 찾은 index로

(2) 위아래로 같은 수마다 1씩 카운트 한것인데

더 개선해야할 방법 부탁드립니다.!

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] nCard = new int[n];
        for(int i = 0 ; i < n ; i++){
            nCard[i] = s.nextInt();
        }
        Arrays.sort(nCard);
        
        int m = s.nextInt();
        int[] mCard = new int[m];
        for(int i = 0 ; i < m ; i++){
            mCard[i] = s.nextInt();
        }
        
        
        StringBuilder sb = new StringBuilder();
		
		for(int j = 0; j < m ; j++) {
			int index = binarySearchIndex(nCard, mCard[j]);
			if(index >= 0) {
				sb.append(countNum(nCard, index, mCard[j])).append(" ");
			}
			else {
				sb.append("0 ");
			}
		}
		System.out.println(sb);
        
    }
    public static int binarySearchIndex(int[] nCard, int num) {
		int start = 0;
		int end = nCard.length -1;
		while(start < end) {
			int mid = (start + end)/2;
			if(nCard[mid] == num) {
				return mid;
			}
			else if(nCard[mid] > num) {
				end = mid;
			}
			else if(nCard[mid] < num) {
				start = mid+1;
			}
		}
		return -1;
	}
	public static int countNum(int[] nCard, int index, int num) {
		int count = 1;
		
		int tmp = index-1;
		while(tmp >= 0) {
			if(nCard[tmp] == num) {count++;
			tmp--;}
			else break;
		}
		tmp = index+1;
		while(tmp < nCard.length) {
			if(nCard[tmp] == num) {count++;
			tmp++;}
			else break;
		}
		
		return count;
	}
}

djm03178 1년 전 1

lower bound와 upper bound에 대해 알아보세요.

jrhopefulp 1년 전 0

이해가 잘 안됩니다 선생님...

djm03178 1년 전 0

구글에 검색을 해보라는 뜻이었습니다. 해당 테크닉들을 알면 풀 수 있습니다.

djm03178 1년 전 1

지금 코드가 시간 초과가 되는 이유만 말씀드리자면, 같은 원소가 엄청나게 많을 경우 이 코드는 한 지점에서 좌우로 엄청나게 많이 확인을 해야 할 것이고, 최악의 경우에는 원소 전체를 보게 될 것입니다. 이를 찾고자 하는 수의 개수만큼 반복하게 되면 약 2500억이니 절대로 시간 내에 통과될 수가 없습니다.

lower buond와 upper bound는 이 문제를 해결해주는 기법입니다.

jrhopefulp 1년 전 0

찾아보고 해결했습니다. 감사합니다!

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

문제

문제

출처

ICPC

Java 시간초과 질문입니다.

jrhopefulp 1년 전 0

djm03178 1년 전 1

jrhopefulp 1년 전 0

djm03178 1년 전 0

djm03178 1년 전 1

jrhopefulp 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말