글 읽기 - 이분탐색으로 풀었는데 반례좀 찾아주세요~

leejy19908036 6년 전 0

이분탐색으로 풀고...테스트 케이스 예시도

맞았는데.. 어디 부분이 틀린걸까요?

	import java.util.*;
	
	public class Main {
		static int[] a;
		static int[] t;
		static int[] result;
	
		public static void main(String args[]) {
			Scanner sc = new Scanner(System.in);
			int m = sc.nextInt();
			t = new int[m];
			for (int i = 0; i < m; i++)
				t[i] = sc.nextInt();
			
			int n = sc.nextInt();
			a = new int[n];
			result = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = sc.nextInt();
			
			Arrays.sort(t);
			binarySearch(m, n);
			
			for(int i : result)
				System.out.print(i+" ");
		}
	
		static void binarySearch(int m, int n) {
	
			for (int i = 0; i < n; i++) {
				int left = 0;
				int right = m- 1;
				int cnt = 0;
				while (left <= right) {
					int mid = (left + right) / 2;
					if(t[mid] == a[i]){
						int temp = mid;
						while(t[mid] == a[i]){
							++cnt;
							if(++mid >= m)
								break;
						}
						mid = temp;
						while(t[--mid] == a[i]){
							++cnt;
							if(--mid < 0)
								break;
						}
						result[i] = cnt;
						break;
					}
					if(a[i] < t[mid])
						right = mid-1;
					else
						left = mid+1;
				}
			}
		}
	}

djm03178 6년 전 0

44번째 줄은 안전하지 않습니다. 처음에 mid가 0이면, 바로 t[-1]에 접근하게 됩니다. 게다가 44~48번째 줄에서는 루프를 한 번 돌 때마다 mid가 두 번 감소하게 됩니다.

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

문제

문제

출처

ICPC

이분탐색으로 풀었는데 반례좀 찾아주세요~

leejy19908036 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말