[백준알고리즘] 이분탐색 응용 - 숫자 카드2 문제

시간초과 코드

 

대략 어떤 식이었냐면

찾고자 하는 수를 먼저 이분탐색으로 인덱스를 알아내고

그 수가 여러개 있을 경우를 생각해서 그 인덱스로부터 앞으로 얼마나 더 있는지, 뒤로 얼마나 더 있는지를

선형탐색식으로 찾아나가는 방법이었으나

탐색 횟수가 커지면 아무래도 시간초과가 뜰만한 방법이었다..

package baekjoonWeek5;

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

public class BJ_10816 {     //백준 숫자카드 2 문제
    static ArrayList<Integer> cards;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());    //카드개수
        cards = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(cards);
        int M = Integer.parseInt(br.readLine());    //찾아야 할 수의 개수
        int[] Mnums = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            Mnums[i] = Integer.parseInt(st.nextToken());
        }

        int sum;
        int findIndex;
        int tmp;
        for (int i = 0; i < M; i++) {
            sum = 0;
            findIndex = BinarySearch(0, cards.size() - 1, Mnums[i]);;  //발견한 인덱스 지점의 앞뒤를 살핀다
            if (findIndex == -1) {  //없다고 나오면 그냥 0 출력하고 넘어감
                bw.write(0 + " ");
                continue;
            }
            tmp = findIndex - 1;

            while (tmp >= 0 && tmp < cards.size() && cards.get(tmp) == Mnums[i]) {    //왼쪽으로 한칸씩 이동하며 탐색
                tmp--;
                sum++;
            }
            tmp = findIndex + 1;
            while (tmp >= 0 && tmp < cards.size() && cards.get(tmp) == Mnums[i]) {    //오른쪽으로 한칸씩 이동하며 탐색
                tmp++;
                sum++;
            }
            sum++;
            bw.write(sum + " ");     //원래의 findIndex자리위치까지 카운트
        }
        bw.flush();
        bw.close();
    }
    static int BinarySearch(int left, int right, int x) {
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (cards.get(mid) == x) {
                return mid;
            }
            if (x > cards.get(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

 

이분검색을 활용해 이 문제를 푸는 열쇠는 x의 하한선(LowerBound), 상한선(UpperBound)을 찾는것이다.

상한선 - 하한선을 하면 정렬된 배열 내에서 x의 개수가 나온다

(배열에 x가 없을경우 하한선과 상한선은 같은 인덱스를 가리키게 되므로 0이 출력된다)

이때 조심할점은 상한선과 하한선을 구할떄 인덱스 0부터 배열의 크기만큼!!(-1하면안됨)봐줘야 올바른 값이 나온다는거다

상한선,하한선을 구하고자 하는 x가 배열 내의 가장 오른쪽 수보다 클 경우를 생각해보면 이해가간다

 

package baekjoonWeek5;

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

public class BJ_10816 {     //백준 숫자카드 2 문제
    static int[] cards;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());    //카드개수
        cards = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cards);
        int M = Integer.parseInt(br.readLine());    //찾아야 할 수의 개수
//        int[] Mnums = new int[M];
        st = new StringTokenizer(br.readLine());
        int toFind = 0;
        int lb; int ub; //하한선, 상한선
        for (int i = 0; i < M; i++) {
            toFind = Integer.parseInt(st.nextToken());
            //lb, ub는 인덱스를 -1해서보면 안된다
            lb = LowerBound(0, cards.length, toFind);
            ub = UpperBound(0, cards.length, toFind);

            bw.write(ub - lb + " ");
        }

        bw.flush();
        bw.close();
    }

    static int LowerBound(int l, int h, int x) {    //하한선, x보다 같거나 큰 수들 중 가장 작은 수 (처음 나타나는 x 이상의 수)
        int mid = 0;
        while (l < h) {
            mid = (l + h) / 2;
            if (cards[mid] == x) {
                h = mid;
            } else if (cards[mid] < x) {
                l = mid + 1;    //찾고자하는 값이 mid 이하로는 없을 것이므로 범위 줄인다
            } else {    //찾고자하는 값이 mid값보다 작다면
                h = mid;
            }
        }
        return l;
    }

    static int UpperBound(int l, int h, int x) {    //상한선, x보다 큰 수들 중 가장 작은 수 (처음 나타나는 x 초과 수)
        int mid = 0;
        while (l < h) {
            mid = (l + h) / 2;
            if (cards[mid] == x) {
                l = mid + 1;
            } else if (cards[mid] < x) {
                l = mid + 1;    //찾고자하는 값이 mid 이하로는 없을 것이므로 범위 줄인다
            } else {    //찾고자하는 값이 mid값보다 작다면
                h = mid;
            }
        }
        return l;
    }

}