[240306] 알고리즘 리부트 25일차 - 백준 1920, 14425 자바

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        String[] pool = new String[n];


        for (int i = 0; i < n; i++) {
            pool[i] = sc.next();
        }

        // 이분 탐색은 정렬된 배열에서 진행 가능함
        Arrays.sort(pool);

        int cnt = 0;

        for (int i = 0; i < m; i++) {
            String thisStr = sc.next();

            int l = 0;
            int r = pool.length - 1;

            while (l <= r) {
                int mid = (l + r) / 2;

                if (pool[mid].compareTo(thisStr) < 0) {
                    l = mid + 1;
                } else if (pool[mid].compareTo(thisStr) > 0) {
                    r = mid - 1;
                } else {
                    cnt++;
                    break;
                }

            }
        }

        System.out.println(cnt);

    }
}

[Part1-Chapter07-Clip01]

이분 탐색이란, 정렬되어 있는 집합(if i<j , a[i]<a[j])에서 원하는 값을 찾는 효율적인 탐색 방법을 말한다. 

초기에 0번 idx를 L로 설정하고 배열의 마지막 원소의 인덱스를 R로 설정한 후에 두 인덱스의 중앙 idx를 M으로 설정한다. 그리고 M번째 원소의 값을 찾고자 하는 값과 비교하여 작다면 L을 M+1로 변경하고, 찾고자 하는 값보다 크다면  R을 M+1로 변경한다. 이렇게 잔존하는 배열 길의의 반씩 줄여가며 탐색을 진행하기 때문에 효율적인 탐색 알고리즘이다. 

- 백준 1920 수 찾기

왜 자꾸 인덱스 오류가 나나 했더니 (l+r)/2가 아니라 l+r/2를 작성했더라. 아는 문제라고 정신 놓고 코드 치지 말자.. 

package BaekJoon.binarysearch;

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

public class BJ1920 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int m = sc.nextInt();

        StringBuilder sb = new StringBuilder();

        while (m-- > 0) {
            int thisNum = sc.nextInt();
            boolean find = false;

            int l = 0;
            int r = arr.length - 1;

//            System.out.println("thisNum: " + thisNum);
//
//            System.out.println("===================================");

            while (l <= r) {
                int mid = (l + r) / 2;

//                System.out.println("l: " + l);
//                System.out.println("r: " + r);
//                System.out.println("mid: " + mid);

                if (arr[mid] < thisNum) l = mid + 1;
                else if (arr[mid] > thisNum) r = mid - 1;
                else if (arr[mid] == thisNum) {
                    sb.append(1 + "\n");
                    find = true;
                    break;
                }

            }
            if (!find) sb.append(0 + "\n");
        }

        System.out.println(sb);

    }

}

그리고 Arrays 라이브러리에 binarySearch 함수가 있다고 해서 아래와 같이 풀어보았다.  값이 존재하지 않는 경우 return 값이 음수로 나와서 아래와 같이 조건문을 작성해서 답을 도출했다.

package BaekJoon.binarysearch;

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

public class BJ1920_1 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int m = sc.nextInt();

        StringBuilder sb = new StringBuilder();

        while (m-- > 0) {
            int thisNum = sc.nextInt();
            if (Arrays.binarySearch(arr, thisNum) >= 0) {
                sb.append(1 + "\n");
            } else {
                sb.append(0 + "\n");
            }
        }

        System.out.println(sb);

    }
}

[Part1-Chapter07-Clip02]

- 백준 14425 문자열 집합

 

문자열을 한 글자씩 비교한다는 생각에 매여서 한참 돌아왔던 것 같다. 이분 탐색을 진행해야 하는데 배열 대신 어레이리스트를 원소로하는 배열을 만들어서 알파벳 순으로 분류해놓고 그 안의 문자열 길이 순으로 정렬된 어레이리스트에서 이분탐색을 진행하려고 했었다. 위에서 말한 것처럼 한글자씩 비교해야 한다는 생각에 일단 문자열의 길이가 같은 문자열의 인덱스를 찾고 인덱스를 기준으로 길이가 같은 모든 문자열을 다 순회하면서 같은 문자열인지 비교하려 했다. 그 코드가 아래코드이다. 길고 험난한 길...을 다녀왔고

package BaekJoon.binarysearch;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class BJ14425_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList[] wordsPool = new ArrayList[27];
        String[] targetWords = new String[m];

        for (int i = 0; i < 27; i++) {
            wordsPool[i] = new ArrayList<String>();
            Collections.sort(wordsPool[i], (Comparator<String>) (o1, o2) -> o1.length() - o2.length());
        }

        for (int i = 0; i < n; i++) {
            String thisStr = sc.next();
            wordsPool[thisStr.charAt(0) - 97].add(thisStr);
        }

        for (int i = 0; i < m; i++) {
            targetWords[i] = sc.next();
        }

        int cnt = 0;

        for (int i = 0; i < m; i++) {
            String thisWord = targetWords[i];
//            System.out.println("thisWord: " + thisWord);
//            System.out.println("thisWord.length: " + thisWord.length());

            int l = 0;
            int r = wordsPool[thisWord.charAt(0) - 97].size() - 1;

            for (int j = 0; j < wordsPool[thisWord.charAt(0) - 97].size(); j++) {


                int mid = (r + l) / 2;

//                System.out.println("(0) l: "+ l);
//                System.out.println("(0) r: "+ r);
//                System.out.println("(0) mid: "+ mid);

                if (wordsPool[thisWord.charAt(0) - 97].get(mid).toString().length() > thisWord.length()) {
                    r = mid - 1;
                } else if (wordsPool[thisWord.charAt(0) - 97].get(mid).toString().length() < thisWord.length()) {
                    l = mid + 1;
                } else {
                    if (findWord(thisWord, mid, wordsPool[thisWord.charAt(0) - 97])) {
                        cnt++;
                        break;
                    }
                }
            }
        }

        System.out.println(cnt);
    }

    private static boolean findWord(String thisWord, int mid, ArrayList wordsPool) {
        boolean find = false;

        for (int i = mid; i >= 0; i--) {

            if (wordsPool.get(i).toString().length() < thisWord.length()) break;

            if (wordsPool.get(i).equals(thisWord)) {
                find = true;
                break;
            }

        }
        if (!find) {

            for (int i = mid; i < wordsPool.size(); i++) {

                if (wordsPool.get(i).toString().length() > thisWord.length()) break;

                if (wordsPool.get(i).equals(thisWord)) {
                    find = true;
                    break;
                }
            }
        }

        if (find) return true;
        else return false;
    }

}

아래 코드가 정답 코드이다. String의 메서드 중 compareTo라는 메서드를 정확히 알고 있지 못했기 때문에 적용하지 못했다. 타겟 문자와 배열의 문자를 비교하면서 compareTo를 사용하면 사전식으로 비교를 진행하고 리턴값이 0과 음수 그리고 양수 세 분류로 나눠진다.

0인 경우 같은 문자라는 뜻이고, 음수인 경우 타겟 문자열 보다 비교 대상의 문자열 가 더 앞쪽에 위치해 있다는 것이며 반대로 양수인 경우 타겟 문자열 보다 비교 대상의 문자열이 더 뒤쪽에 위치한다는 의미이다. 이 부분을 활용해서 l과 r의 인덱스 위치를 조정하면 각 문자열을 직접 비교하는 로직 없이 문제를 해결할 수 있다.

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        String[] pool = new String[n];


        for (int i = 0; i < n; i++) {
            pool[i] = sc.next();
        }

        // 이분 탐색은 정렬된 배열에서 진행 가능함
        Arrays.sort(pool);

        int cnt = 0;

        for (int i = 0; i < m; i++) {
            String thisStr = sc.next();

            int l = 0;
            int r = pool.length - 1;

            while (l <= r) {
                int mid = (l + r) / 2;

                if (pool[mid].compareTo(thisStr) < 0) {
                    l = mid + 1;
                } else if (pool[mid].compareTo(thisStr) > 0) {
                    r = mid - 1;
                } else {
                    cnt++;
                    break;
                }

            }
        }

        System.out.println(cnt);

    }
}