글 읽기 - 어떤 문제가 생긴걸까요??

chon56 6년 전 0

A와 B배열의 입력된 값을 AB배열에 저장하고

C와 D배열의 입력된 값을 CD배열에 저장했습니다.

이분 탐색법을 통해 count 를 계산했습니다.

7%정도에서 틀렸습니다가 나오는데 제가 생각하지 못한 경우의 수가 있을까요??

import java.util.*;
public class Main20 {
	static Scanner scan = new Scanner(System.in);
	static int n = scan.nextInt();
	
	static int[] A = new int[n];
	static int[] B = new int[n];
	static int[] C = new int[n];
	static int[] D = new int[n];
	
	static int[] AB = new int[n*n];
	static int[] CD = new int[n*n];
	
	static int count = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for(int i=0; i<n; i++) {
			A[i] = scan.nextInt();
			B[i] = scan.nextInt();
			C[i] = scan.nextInt();
			D[i] = scan.nextInt();
		}
		
		int k = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				AB[k] = A[i]+B[j];
				CD[k] = C[i]+D[j];
				k++;
			}
		}
		Arrays.sort(AB);
		Arrays.sort(CD);
		for(int i=0; i<AB.length; i++) {
			count += binarySearch(-AB[i], CD);
		}
		System.out.println(count);
	}
	
	private static int binarySearch(int num, int[] CD) {
		// TODO Auto-generated method stub
		int left = 0;
		int right = CD.length-1;
		
		while(left <= right) {
			int mid = (left+right)/2;
			
			if(num == CD[mid]) {
				//count++;
				return 1;
			}
			
			if(num <= CD[mid]) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return 0;
	}
}

djm03178 6년 전 1

0 0 0 0

정답은 16인데, 4가 출력됩니다.

chon56 6년 전 0

애초에 이문제는 binary Search로 접근하는게 잘못된 생각인가요??

djm03178 6년 전 2

이분탐색까지는 좋으나, 값이 여러 개 있을 수 있다는 점을 고려해야 합니다. 좀 더 명확히 하자면, "x가 처음으로 나오는 지점"과 "x가 마지막으로 나오는 지점"을 모두 계산해야 됩니다. C++의 경우 equal_range라는 아주 간편한 함수가 있지만, Java는 모르겠네요.

chon56 6년 전 0

역시... djm03178님의 도움은 정말 많은걸 깨닫게 해주네요.

해결했습니다...

upper함수와 lower함수를 만들어 upper -> x가 마지막으로 나온 지점 , lower -> x가 처음으로 나온 지점

count변수에 upper-lower의 값을 더해주니 맞았습니다가 나오네요.

2일동안 삽질해서 많은것을 배워갑니다

추가로 C++의 equal_range함수는 lower와 upper의 값을 한번에 뽑아주는 함수인가요??

djm03178 6년 전 1

함수 이름 그대로, 정렬된 배열에서 특정한 값이 나타나는 범위를 반환해줍니다.

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

문제

문제

출처

ICPC

어떤 문제가 생긴걸까요??

chon56 6년 전 0

djm03178 6년 전 1

chon56 6년 전 0

djm03178 6년 전 2

chon56 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말