글 읽기 - 자바 Collections.binarySearch() 이용했는데 틀렸습니다..

gpejvkdlf17 1년 전 0

Collections.binarySearch() 는 찾으려는 값이 없으면 음수(-(insertion point)-1), 있으면 인덱스를 return 해주고,

이 때 찾으려는 값이 탐색 대상이 되는 배열(또는 리스트 등) 내에 1개 이상 존재한다면

존재하는 위치 중 가장 먼저 찾은 인덱스를 return 해 주는 것으로 알고있습니다.

아래 코드에서,

탐색 대상이 되는 정렬된 리스트를 listB, 찾으려는 값을 value 라고 할 때,

value가 listB에 없는 경우는 진행 하지 않고,

value가 listB에 있는 경우 (반환된 인덱스가 0 이상의 정수인 경우)

인덱스를 좌우로 넓혀가며

listB.get(좌)==value 를 만족하는 가장 왼쪽의 인덱스와

listB.get(우)==value 를 만족하는 가장 오른쪽의 인덱스를 각각 구해서

(우-좌)+1 의 누적합을 정답으로 판단했습니다.

이 방식 자체에는 문제가 없다고 생각하는데,

혹시 아래 코드에 제가 식별하지 못한 예외나 오류가 있을까요?

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static Long T;

	public static void main(String[] args) throws IOException {
		List<Long> listA = new ArrayList<>();
		List<Long> listB = new ArrayList<>();
		
		T = Long.parseLong(br.readLine());
		
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			listA.add(Long.parseLong(st.nextToken()));
		}
		
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < m; i++) {
			listB.add(Long.parseLong(st.nextToken()));
		}
		
        // listA, listB 각각 누적합 계산
		find(listA, n);
		find(listB, m);
		
        // 정렬
		Collections.sort(listB);
		Collections.sort(listA);
		
		long answer = 0;
		
		for(int i = 0; i < listA.size(); i++) {
			Long value = T-listA.get(i);
			int index = Collections.binarySearch(listB, value);
			
			if(index < 0) continue;		// listB 에 value 가 없으면 패스
			
			int s = index;
			int e = index;
			
			while(listB.get(s)==value) {
				s--;
				if(s<0) break;
			}
			s++;
			
			while(listB.get(e)==value) {
				e++;
				if(e>listB.size()-1) break;
			}
			e--;
			
			answer += (e-s)+1;
		}
		
		bw.write(answer+"");
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void find(List<Long> list, int size) {
		for(int i = 0; i < size; i++) {
			long sum = list.get(i);
			for(int j = i+1; j < size; j++) {
				sum += list.get(j);
				list.add(sum);
			}
		}
	}
}

luizy991212 1년 전 1

존재하는 수 중에서 아무위치가 출력됩니다. 그래서 저는 찾은 위치중 가작 작은값만 출력 할 수 있게 코드를 새로 짰습니다.

제 코드 참고가 될까해서 남겨놓습니다.

https://github.com/LuizyHub/Be...

다만, 이문제는 HashMap을 이용하는게 가장 효율적일거같아요.

    private static int binarySearch(int[] a, int key){
        return binarySearch0(a,0,a.length,key);
    }
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            if (low == high && a[low] == key)
                return low;
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else //midVal == key
                high = mid;
        }
        return -(low+1);  // key not found.
    }

luizy991212 1년 전 1

이건 자바에서 지원하는 BinarySerach입니다.

* multiple elements with the specified value, there is no guarantee which
* one will be found.

9,10번째 문장과같이 어떤 위치를 반환할지는 보장되지 않는다고하네요

    /**
     * Searches a range of
     * the specified array of ints for the specified value using the
     * binary search algorithm.
     * The range must be sorted (as
     * by the {@link #sort(int[], int, int)} method)
     * prior to making this call.  If it
     * is not sorted, the results are undefined.  If the range contains
     * multiple elements with the specified value, there is no guarantee which
     * one will be found.
     *
     * @param a the array to be searched
     * @param fromIndex the index of the first element (inclusive) to be
     *          searched
     * @param toIndex the index of the last element (exclusive) to be searched
     * @param key the value to be searched for
     * @return index of the search key, if it is contained in the array
     *         within the specified range;
     *         otherwise, <code>(-(<i>insertion point</i>) - 1)</code>.  The
     *         <i>insertion point</i> is defined as the point at which the
     *         key would be inserted into the array: the index of the first
     *         element in the range greater than the key,
     *         or {@code toIndex} if all
     *         elements in the range are less than the specified key.  Note
     *         that this guarantees that the return value will be &gt;= 0 if
     *         and only if the key is found.
     * @throws IllegalArgumentException
     *         if {@code fromIndex > toIndex}
     * @throws ArrayIndexOutOfBoundsException
     *         if {@code fromIndex < 0 or toIndex > a.length}
     * @since 1.6
     */
    public static int binarySearch(int[] a, int fromIndex, int toIndex,
                                   int key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return binarySearch0(a, fromIndex, toIndex, key);
    }

    // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

gpejvkdlf17 1년 전 0

오.. 제가 잘못 알고 있었군요! 감사합니다

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

문제

문제

출처

ICPC

자바 Collections.binarySearch() 이용했는데 틀렸습니다..

gpejvkdlf17 1년 전 0

luizy991212 1년 전 1

luizy991212 1년 전 1

gpejvkdlf17 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말