글 읽기 - 이분탐색에서 어디가 문제인지 모르겠습니다.

s48011 6년 전 1

카드의 수들을 card 어레이리스트에 넣었습니다.

리스트들을 list 어레이리스트에 넣었습니다.

결과를 저장할 result배열을 생성하고,

card를 정렬한 다음, list의 값 하나씩을 card에서 찾고,

존재하면 result에 1을, 존재하지 않으면 0을 넣었습니다.

이분탐색으로 구현했는데, 틀렸다고 나오는데 어디서 잘못된건지 전혀모르겠습니다.

import java.util.*;
public class Number_Card {
	static ArrayList<Integer> card;
	static ArrayList<Integer> list;
	
	public static boolean Binary_Search(Integer data, ArrayList<Integer> check){
		int left = 0;
		int right = check.size()-1;
		
		while(left <= right){
			int mid = (left + right)/2;
			if(check.get(mid) == data){
				return true;
			}
			else if(check.get(mid) > data){
				right = mid - 1;
			}
			else{
				left = mid + 1;
			}
		}
		return false;
	}
	
	public static void main(String[] args){
		Scanner read = new Scanner(System.in);
		
		int n;
		n = read.nextInt();
		card = new ArrayList<>();
		
		int num;
		
		for(int i = 0; i < n; i++){
			num = read.nextInt();
			card.add(num);
		}
		
		int m;
		m = read.nextInt();
		list = new ArrayList<Integer>();

		for(int i = 0; i < m; i++){
			num = read.nextInt();
			list.add(num);
		}

		Collections.sort(card);
		int result[] = new int[m];
		
		for(int i = 0; i < m; i++){
			boolean check = Binary_Search(list.get(i), card);
			if(check)
				result[i] = 1;
			else
				result[i] = 0;
		}
		
		for(int i = 0; i < m; i++)
			System.out.print(result[i] + " ");
	}
}

chogahui05 6년 전 1

잘못된 건 없는 거 같은데?? 잘 보시면요.

Integer 객체랑 Integer 객체랑 비교하고 있어요.

객체랑 객체랑 비교하는 경우, 가리키는 주솟값이 달라서 false가 리턴됩니다.

Integer 클래스 안에 있는 intValue 메서드는 Integer 객체의 정수 값을 리턴해주는 함수입니다.

아니면 equal 메서드를 쓸 수 있겠지만, 이분탐색의 특성상. 그냥 아래와 같이 intValue 메서드를 쓰는게 적합해 보입니다.

public static boolean Binary_Search(Integer data, ArrayList<Integer> check){
		int left = 0;
		int right = check.size()-1;
		
		while(left <= right){
			int mid = (left + right)/2;
			if(check.get(mid).intValue() == data.intValue()){
				return true;
			}
			else if(check.get(mid).intValue() > data.intValue()){
				right = mid - 1;
			}
			else{
				left = mid + 1;
			}
		}
		return false;
	}

chogahui05 6년 전 1

참고하시면 좋으실 것 같아서 올려봅니다.

http://stackoverflow.com/quest...

s48011 6년 전 0

해결했습니다!! 두분 모두 감사드립니다

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

문제

문제

출처

ICPC

이분탐색에서 어디가 문제인지 모르겠습니다.

s48011 6년 전 1

chogahui05 6년 전 1

chogahui05 6년 전 1

s48011 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말