글 읽기 - 이분탐색 알고리즘 어디를 수정해야 시간초과가 안날까요..?

leejy19908036 6년 전 0

이분탐색 알고리즘 어디를 수정해야 시간초과가 안날까요..?

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

public class Main {
	static int[] a;
	static int[] t;
	static StringBuilder result;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		result = new StringBuilder();
		int m = Integer.parseInt(br.readLine());
		t = new int[m];
		String st[] = br.readLine().split(" ");
		for (int i = 0; i < m; i++)
			t[i] = Integer.parseInt(st[i]);

		int n = Integer.parseInt(br.readLine());
		String st1[] = br.readLine().split(" ");
		a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st1[i]);

		Arrays.sort(t);
		for (int i = 0; i < n; i++) {
			result.append(binarySearch(0, m - 1, 0, a[i]) + " ");
		}

		OutputStreamWriter bw = new OutputStreamWriter(System.out);
		bw.write(result.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	static int binarySearch(int left, int right, int cnt, int ans) {

		int mid = (left + right) / 2;
		int result;
		if(left > right)
			return cnt;
		else{
	        if (t[mid] > ans){
	            result = binarySearch(left, mid-1, cnt, ans);
	        }
	        else if (t[mid] < ans)
	        {
	            result = binarySearch(mid +1, right, cnt, ans);
	        }
	        else{
	        
	            result = binarySearch(left, mid - 1, cnt, ans);
	            result += binarySearch(mid + 1, right, cnt, ans);
	            result += 1;
	        }
	 
	        return result;
	    }
	}
}

djm03178 6년 전 2

52~54줄처럼 하면 결국 최악의 경우 전체를 탐색하게 됩니다. 이 문제는 lower bound와 upper bound를 구현해야 하는 문제입니다.

leejy19908036 6년 전 0

감사합니다~새로운 부분을 알았습니다!!

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

문제

문제

출처

ICPC

이분탐색 알고리즘 어디를 수정해야 시간초과가 안날까요..?

leejy19908036 6년 전 0

djm03178 6년 전 2

leejy19908036 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말