[BOJ] 이분 탐색 단계 - JAVA

이분 탐색 단계

• 수 찾기
• 숫자 카드2
• 랜선 자르기
• 나무 자르기

 

 ▷수 찾기 

www.acmicpc.net/problem/1920

1920번: 수 찾기

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Main m = new Main();
        int num_size = Integer.parseInt(br.readLine().trim());
        int[] arr = new int[num_size];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<num_size; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        
        int input_size = Integer.parseInt(br.readLine().trim());
        StringTokenizer input_st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<input_size; i++){
            int findNum = Integer.parseInt(input_st.nextToken());
            m.binarySearch(arr, findNum, 0, num_size-1, bw);
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    
    public void binarySearch(int[] arr, int k , int start, int end, BufferedWriter bw) throws IOException {
        int middle = (start + end)/2;
        if(middle < start || middle > end) {
        	bw.write("0");
        }
        else{
            if(k == arr[middle]) {
                bw.write("1");
            }
            else if( k < arr[middle] ) {
                binarySearch(arr, k, start, middle-1, bw);
            }
            else if( k > arr[middle] ) {
                binarySearch(arr, k, middle+1, end, bw);
            }
        }
    }
}

런타임 에러나 컴파일 에러만 발생하고 딱히 틀리지 않았다.

N개의 수를 받아 배열에 담고 이를 배열이 가진 함수를 사용하여 정렬한 뒤, 이분 탐색법을 사용하여 주어진 값 K 가 존재하는지 확인 한다.

 ▷ 숫자 카드 2 

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

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

public class Main{
    static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public static void main(String[] args) throws IOException{
        Main m = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        for(int i = 0; i<N; i++){
            int n = Integer.parseInt(st.nextToken());
            if(!map.containsKey(n)) map.put(n, 1);
            else map.put(n, map.get(n)+1);
        }
        
        Object[] mapKeys = map.keySet().toArray();
        Arrays.sort(mapKeys);
        
        int input_n = Integer.parseInt(br.readLine().trim());
        StringTokenizer input_st = new StringTokenizer(br.readLine(), " ");
        
        for(int i = 0; i<input_n; i++){
            int findN = Integer.parseInt(input_st.nextToken());
            m.binarySearch(mapKeys, findN, 0, mapKeys.length-1, bw);
        }
    }
    
    public void binarySearch(Object[] arr, int k , int start, int end, BufferedWriter bw) throws IOException {
        int middle = (start + end)/2;
        int value = (int)arr[middle];
        if(middle < start || middle > end) {
        	bw.write("0\n");
        }
        else{
            if(k == value) {
                bw.write(map.get(value)+"\n");
            }
            else if( k < value ) {
                binarySearch(arr, k, start, middle-1, bw);
            }
            else if( k > value ) {
                binarySearch(arr, k, middle+1, end, bw);
            }
        }
    }
}

위의 코드는 처음 제출 했을때 틀렸다고 나온 코드이다.

이유는 main함수 안에 bw.flush(), bw.close(), br.close()함수를 명시하지 않았기 때문이다...

항상 이런 자잘한 실수로 한번에 맞추는걸 실패하곤 한다.

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

public class Main{
    static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public static void main(String[] args) throws IOException{
        Main m = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        for(int i = 0; i<N; i++){
            int n = Integer.parseInt(st.nextToken());
            if(!map.containsKey(n)) map.put(n, 1);
            else map.put(n, map.get(n)+1);
        }
        
        Object[] mapKeys = map.keySet().toArray();
        Arrays.sort(mapKeys);
        
        int input_n = Integer.parseInt(br.readLine().trim());
        StringTokenizer input_st = new StringTokenizer(br.readLine(), " ");
        
        for(int i = 0; i<input_n; i++){
            int findN = Integer.parseInt(input_st.nextToken());
            m.binarySearch(mapKeys, findN, 0, mapKeys.length-1, bw);
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
    
    public void binarySearch(Object[] arr, int k , int start, int end, BufferedWriter bw) throws IOException {
        int middle = (start + end)/2;
        int value = (int)arr[middle];
        if(middle < start || middle > end) {
        	bw.write("0\n");
        }
        else{
            if(k == value) {
                bw.write(map.get(value)+"\n");
            }
            else if( k < value ) {
                binarySearch(arr, k, start, middle-1, bw);
            }
            else if( k > value ) {
                binarySearch(arr, k, middle+1, end, bw);
            }
        }
    }
}

위의 코드는 맞는 코드이다.

 

 ▷ 랜선 자르기 

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

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

public class Main{
	static ArrayList<Integer> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        Main m = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int haveLan = Integer.parseInt(st.nextToken());
        int wantLan = Integer.parseInt(st.nextToken());
        
        for(int i = 0; i<haveLan; i++){
             int lan_size = Integer.parseInt(br.readLine().trim());
             arr.add(lan_size);
        }
        
        int min_size = Collections.min(arr);
        
        m.binarySearch(min_size, wantLan, 1, min_size, bw);
        
        bw.flush();
        bw.close();
        br.close();
    }
    
    public void binarySearch(int preValue, int wantLan , int start, int end, BufferedWriter bw) throws IOException {
        int middleValue = (start + end)/2;
        int sum = 0;
        
        if(middleValue > start && middleValue < end) {
        	for(int i : arr){
        		sum += i/end;
        	}
        	if(sum > wantLan) binarySearch(end, wantLan, end, preValue, bw);
        	else if(sum < wantLan) binarySearch(end, wantLan, start, middleValue, bw );
        	else if(sum == wantLan) bw.write(end+"\n");
        }
        else{
            bw.write(preValue+"\n");
        }
    }
}

위의 코드는 실패한 코드이다. 첫번째로 나는 반드시 제일 작은 길이도 포함된다라고 생각해서 최소값을 기준으로 했다. 근데 문제에서는 가장 길게 원하는 랜선 개수를 맞추는 것이기 때문에 조건에 따라 가장 작은 랜선이 포함이 되지 않을 수 있다.

이점을 파악하지 못한게 가장 큰 실수 였다.

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

public class Main{
	static ArrayList<Integer> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        Main m = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int haveLan = Integer.parseInt(st.nextToken());
        int wantLan = Integer.parseInt(st.nextToken());
        for(int i = 0; i<haveLan; i++){
            int lan_size = Integer.parseInt(br.readLine().trim());
            arr.add(lan_size);
        }
        
        int max_size = Collections.max(arr);
        
        m.binarySearch(max_size, wantLan, 1, max_size, bw);
        bw.flush();
        bw.close();
        br.close();
    }
    
    public void binarySearch(int preValue, int wantLan , int start, int end, BufferedWriter bw) throws IOException {
        int middleValue = (start + end)/2;
        long sum = 0;
        for(int i : arr){
        	sum += i/end;
        }
        if(start == end && sum >= wantLan) {
        	bw.write(end+"\n");
        	return ;
        }else if(start == end && sum < wantLan){
        	bw.write("-1\n");
        	return ;
        }
        if(sum >= wantLan) binarySearch(preValue, wantLan, end, preValue, bw);
        if(sum < wantLan) binarySearch(end, wantLan, start, middleValue, bw );
    }
}

위의 코드는 맞는 코드이다. 가장 큰 값을 기준으로 이분 탐색하여 값의 범위를 정해준다. 오늘 푼 문제중 가장 틀린 횟수가 많은 문제였는데 이유는 문제를 제대로 파악하지 못했다는 점에 있다.

 ▷ 나무 자르기 

www.acmicpc.net/problem/2805

2805번: 나무 자르기

이 문제는 랜선 자르기와 비슷하다고 보면 된다.

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

public class Main{
	static ArrayList<Integer> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        Main m = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int numberOfTree = Integer.parseInt(st.nextToken());
        int wantLength = Integer.parseInt(st.nextToken());
        StringTokenizer tree_st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<numberOfTree; i++){
            int tree_size = Integer.parseInt(tree_st.nextToken());
            arr.add(tree_size);
        }
        
        int max_size = Collections.max(arr);
        
        m.binarySearch(max_size, wantLength, 1, max_size, bw);
        bw.flush();
        bw.close();
        br.close();
    }
    
    public void binarySearch(int preValue, int wantLength , int start, int end, BufferedWriter bw) throws IOException {
        int middleValue = (start + end)/2;
        long sum = 0;
        for(int i : arr){
            if(i > end)
        	    sum += i-end;
        }
        if(start == end && sum >= wantLength) {
        	bw.write(end+"\n");
        	return ;
        }else if(start == end && sum < wantLength){
        	bw.write("-1\n");
        	return ;
        }
        if(sum >= wantLength) binarySearch(preValue, wantLength, end, preValue, bw);
        if(sum < wantLength) binarySearch(end, wantLength, start, middleValue, bw );
    }
}

위의 코드는 틀린 코드인데 이유는 처음 탐색할 때 범위의 값이 0부터 진행되어야 하는데 1부터 넣었기때문이다.

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

public class Main{
	static ArrayList<Integer> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        Main m = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int numberOfTree = Integer.parseInt(st.nextToken());
        int wantLength = Integer.parseInt(st.nextToken());
        StringTokenizer tree_st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<numberOfTree; i++){
            int tree_size = Integer.parseInt(tree_st.nextToken());
            arr.add(tree_size);
        }
        
        int max_size = Collections.max(arr);
        
        m.binarySearch(max_size, wantLength, 0, max_size, bw);
        bw.flush();
        bw.close();
        br.close();
    }
    
    public void binarySearch(int preValue, int wantLength , int start, int end, BufferedWriter bw) throws IOException {
        int middleValue = (start + end)/2;
        long sum = 0;
        for(int i : arr){
            if(i > end)
        	    sum += i-end;
        }
        if(start == end && sum >= wantLength) {
        	bw.write(end+"\n");
        	return ;
        }else if(start == end && sum < wantLength){
        	bw.write("-1\n");
        	return ;
        }
        if(sum >= wantLength) binarySearch(preValue, wantLength, end, preValue, bw);
        if(sum < wantLength) binarySearch(end, wantLength, start, middleValue, bw );
    }
}

따라서 범위만 조정하면 맞는 코드가 된다.