1920번 문제 : 수 찾기

1920번: 수 찾기 (acmicpc.net)

1920번: 수 찾기

생각보다 간단해보이지만 시간이 짧다.

시간 단축을 위해 이진탐색으로 풀어야하겠고 조건에 정수의 범위 따지는 거 보니까 자료형도 중요하겠다 mid값은 low+high니까 long형을 써야되겠어

 

이진탐색이 필요할까 싶어서 그냥 구현해봤는데 역시 시간초과가 나왔따 필요하넹 ㅋ

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		int arr[] = new int[num];
		int arr1[] = new int[num];
		int result[] = new int[num];
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<num;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int num1 = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<num1;i++) {
			arr1[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0;i<num1;i++)
		{int val=0;
			for(int j=0;j<num;j++) {
				if(arr[j] == arr1[i]) {
					sb.append(1+"\n");
					val=1;
				}
			}
			if(val==0)
				sb.append(0+"\n");
		}
		System.out.println(sb);
	}
}

탐색을 하는 조건에서 arr1[i]번째의 요소를 모든 arr[]배열과 비교하지말고 arr배열을 정렬한 다음에 이진탐색 이용해야겠다.

 

정수의 범위는 -231 보다 크거나 같고 231보다 작다. ==> int형으로 케어가능............

mid,high,low를 인덱스로 하여 이진탐색을해서 예제 입력출력 잘 나오는 거 확인 ! 근데 틀렸대..

암튼 코드

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		List <Integer>arr = new ArrayList<>(); 
		List <Integer>arr1 = new ArrayList<>();
		int mid;
		
		int val = 0;
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<num;i++) {
			arr.add(Integer.parseInt(st.nextToken()));
		}
		
		int num1 = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<num1;i++) {
			arr1.add(Integer.parseInt(st.nextToken()));
		}
		Collections.sort(arr); //10의 자리 구분 못 함

		int j=0;
		//이진탐색 인덱스(mid,high,low)로 탐색 !!!!!!!!
		for(int k=0;k<num;k++) {
			int high = num-1;
			int low = 0;
			
			while(low<=high) {
				mid = (low+high) /2;
				val = 0;
				if(arr1.get(j) == arr.get(mid)) {
					sb.append(1+"\n");
					val=1;
					j++;
					break;
				}
				else if(arr1.get(j) > arr.get(mid))//key>mid
					low = mid+1;
				else //key<mid
					high = mid-1;
			}
			if(val ==0) {
				sb.append(0+"\n");
				j++;
			}
		}
		System.out.print(sb);
	}
}

10의자리 구분 못 하던 거 때문인가?ㄴㄴㄴㄴㄴㄴㄴㄴㄴㄴㄴㄴㄴ

아 while위 반복문에 num1만큼 반복하는 걸로 바꿔야함 근데 또 틀렸다네 왜징...

반례 넣어봐도 다 된다고 하는데 뭘까 ?

 

뭐지 ????? ArrayList를 배열로 바꾸니까 맞았대 

ㅡㅡ 뭐지 ㅡㅡㅡㅡㅡ 짜증

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		int []arr = new int[num]; 
		
		int val = 0;
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<num;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		int num1 = Integer.parseInt(br.readLine());
		int []arr1 = new int[num1];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<num1;i++) {
			arr1[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr); 

		int j=0;
		//이진탐색 인덱스(mid,high,low)로 탐색 !!!!!!!!
		for(int k=0;k<num1;k++) {
			int high = num-1;
			int low = 0;
			
			while(low<=high) {
				int mid = (low+high) /2;
				val = 0;
				if(arr1[j] == arr[mid]) {
					sb.append(1+"\n");
					val=1;
					j++;
					break;
				}
				else if(arr1[j] > arr[mid])//key>mid
					low = mid+1;
				else //key<mid
					high = mid-1;
			}
			if(val ==0) {
				sb.append(0+"\n");
				j++;
			}
		}
		System.out.print(sb);
	}
}

질문게시판에 질문 남겨놨다 너무 궁금하다 이유

글 읽기 - 너무 궁금해요!) ArrayList 코드를 배열로 바꾸니까 오류가 안 납니다 (acmicpc.net)