[1일1커밋 8D] 아자아자 | 유형별 풀이(2) 이진탐색 ing | 백준 JAVA 1920, 10816

매일매일 한문제씩이라도 풀면서 감 잃지 않기를 바라는 마음으로 다시 시작 (8D라고 쓰는게 의미가 있나ㅎ)

 

[BAEKJOON 백준] 문제 > 단계별풀이 > 이분 탐색 https://www.acmicpc.net/step/29

 

* 이분 탐색, 이진 탐색 (Binary Search)

탐색 범위를 절반씩 좁혀가며 문제를 해결하는 방식으로, 배열 내부 데이터가 정렬이 된 경우에만 사용할 수 있다.

3개의 인덱스(시작, 끝, 절반)를 사용하며 탐색하며, 찾으려는 데이터와 중간값을 끊임없이 비교하며 원하는 값을 찾는 것이 포인트

https://hcr3066.tistory.com/23

 

 

1920. 수 찾기 (실버4) https://www.acmicpc.net/problem/1920

1트 코드는 메모리 초과로 인해 실패, 관련해서 찾아본 글 https://www.acmicpc.net/board/view/84136

Merge Sort의 경우 정렬하는 과정에서 
int[] sorted = new int[A.length];
이와 같이 추가적인 배열을 선언해야 되기 때문에 O(n log n)로 속도가 빠르더라도 배열의 크기가 길어지면 그 만큼 차지하는 메모리의 공간이 늘어나서 메모리 초과가 나는 것 같습니다.

위의 글 보고 정렬하는 메서드를 바꾸고 조건문을 좀 바꿨더니 2트는 또 런타임에러임

이것저것 조건을 다시 보다가 결국 3트만에 해결!

public class Main {

	static int[] a;
	static int[] find;
	static int ans=0;
	static int n, m;
 	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		a = new int[n];
		for(int i=0; i<n; i++) a[i]=sc.nextInt();
		m = sc.nextInt();
		find = new int[m];
		for(int i=0; i<m; i++) find[i]=sc.nextInt();
		
        
		// Collections.sort(a);
		Arrays.sort(a);
		int start=0, end=n-1, mid=n/2;
		for(int i=0; i<m; i++) {
			ans=0;
			if(a[0]<=find[i] && a[n-1]>=find[i]) findA(start, end, mid, find[i]);
			System.out.println(ans);
		}
		
		
	} 
 	
 	static void findA(int start, int end, int mid, int x) {
    	if(start<0 || end >= n || start>=end) return;
 		if(a[mid]==x || a[end]==x || a[start]==x) {
 			ans=1;
 			return;
 		} else if(a[mid]<x) {
 			findA(mid+1, end, (mid+end)/2, x);
 		} else {
 			findA(start, mid-1, (mid+start)/2, x);
 		}
        
         		
 	}
}

그러고 구글링하다 보니 자바에는 이미 이진탐색(binarySearch()) 메서드가 있도라. 꼭 정렬된 배열에 사용할 것!!

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int[] a;
	static int[] find;
	static int ans=0;
	static int n, m;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		a = new int[n];
		for(int i=0; i<n; i++) a[i]=sc.nextInt();
		m = sc.nextInt();
		find = new int[m];
		for(int i=0; i<m; i++) find[i]=sc.nextInt();
		
		Arrays.sort(a);
		for(int i=0; i<m; i++) {
			ans=(Arrays.binarySearch(a, find[i]) <0 ? 0 : 1);
			System.out.println(ans);
		}
	}
}

이렇게 쉽게 풀릴 문제였었는데..

 

10816. 숫자 카드2 (실버4) https://www.acmicpc.net/problem/10816

꼭 이진탐색으로 풀어야하나 싶었지만, 유형이 이진탐색으로 분류된데에는 이유가 있지 않을까 싶어 고민하다 혼자 해결 못함

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

public class Main {

	static int n, m;
	static int[] arr1, arr2;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		arr1 = new int[n]; // 상근 
		st = new StringTokenizer(br.readLine());
		int idx=0;
		while(st.hasMoreTokens()) {
			arr1[idx] = Integer.parseInt(st.nextToken());
			idx++;
		}
        
		m = Integer.parseInt(br.readLine());
		arr2 = new int[m]; // 찾는 카드 
		idx=0;
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens()) {
			arr2[idx] = Integer.parseInt(st.nextToken());
			idx++;
		}
		
		Arrays.sort(arr1);
		
		for(int i=0; i<m; i++) {
			int ans = upper(arr2[i])-lower(arr2[i]);
			sb.append(ans+" ");
		}
		System.out.println(sb);
			
		br.close();
	}
	
	static int lower(int x) {
		int start = 0;
		int end = n;
		
		while(start<end) {
			int mid = (start+end)/2;
			if(x <= arr1[mid]) {
				end = mid;
			} else {
				start = mid+1;
			}
		}
		
		return end;
	}
	
	static int upper(int x) {
		int start = 0;
		int end = n;
		
		while(start<end) {
			int mid = (start+end)/2;
			if(x < arr1[mid]) {
				end = mid;
			} else {
				start = mid+1;
			}
		}
		
		return end;
	}
}

첫번째 문제와 다르게 수를 찾고 끝내는게 아니라 그 수가 나타나는 구간을 찾아 총 개수를 구해야하는 문제이다.

그러다보니 배열 정렬 후 찾는 수가 발견되는 시작 인덱스(lower)와 마지막으로 발견되는 마지막 인덱스(upper)를 구해 그 구간 길이를 구해준다.

이해가 잘 되지 않아 요기 블로그를 참고했다. https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

• lower()
  하한은 찾고자 하는 값 이상의 값이 처음 나타나는 위치를 말한다. 여기서 중요한 것은 '이상' 이다.
  왼쪽 배열 인덱스 0부터 볼때 값이 같거나 큰 경우여야 처음 만나는 위치를 알 수 있다.
• upper()
  상한은 찾고자 하는 값을 초과하는 값을 처음 만나는 위치를 말한다. 마찬가지로 중요한 것은 '초과'이다.
  하한과 반대로 찾고자 하는 값보다 큰 값을 찾아야하며 이 말은 반대로 찾고자 하는 값이 더 이상 넘어갈 수 없는 위치이기도 하다.
• 찾는 값이 없는 경우
  찾는 값이 없을때 lower와 upper은 동일한 값을 출력한다. 
  lower에서 찾고자 하는 값 이상의 인덱스를 반환하는데, 찾고자 하는 값이 없음으로 초과하는 값의 인덱스를 뱉어내고 upper도 똑같이 초과하는 값을 냄으로 두 인덱스는 동일하다.

 

아래는 대충 야매로 풀어서 시도하고 싶었던 코드.. 런타임에러(ArrayIndexOutOfBounds)로 실패함

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

public class Main {

	static int n, m;
	static int[] arr1, arr2;
	static int[] cnt;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		arr1 = new int[n]; // 상근 
		st = new StringTokenizer(br.readLine());
		int idx=0;
		int max = Integer.MIN_VALUE;
		while(st.hasMoreTokens()) {
			arr1[idx] = Integer.parseInt(st.nextToken());
			idx++;
			max = Math.max(max, arr1[idx]);
		}
		
		m = Integer.parseInt(br.readLine());
		arr2 = new int[m]; // 찾는 카드 
		idx=0;
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens()) {
			arr2[idx] = Integer.parseInt(st.nextToken());
			idx++;
		}
		
		cnt = new int[max+1];
		for(int i=0; i<=n; i++) {
			cnt[arr1[i]]++;
		}
		
				for(int i=0; i<m; i++) {
			if(max<arr2[i]) sb.append(0);
			else sb.append(cnt[arr2[i]]);
		}
		System.out.println(sb);
		
		br.close();
	}
}

파이썬때부터 HashMap 만들어 빈도수 저장하고 찾는 그런 풀이를 자주 쓰는데 별로 안좋은거같아서 최근에는 문제 유형에 맞게 풀려고 노력중이다.

대충 되지 않을까 했는데 왜 안되는지 모르겠당 ㅜㅡ

 

하나 더 풀고싶은데 내일 출근 못할거같아서 오늘은 끝! 주말 내내 2문제 푼게 말이 되나 내일부턴 열심히 할거다 (아마도)