[BOJ][JAVA] 10816: 숫자 카드 2

 

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main{
    public static int binarySearch(int[] arr, int target){
        int l=0; int r = arr.length-1;
        int len = 0;
        while (l<=r){
            int m = (l+r)/2;
            if(arr[m]<=target){
                l = m+1;
                if(arr[m] == target) len++;
            }
            else if(arr[m]>=target)
            {
                r = m-1;
                if(arr[m] == target) len++;
            }
        }
        return len;
    }

    public static void main(String[] args) throws Exception{
        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();
        for(int i=0; i<m;i++){
            int tmp = sc.nextInt();
            System.out.print(binarySearch(arr,tmp)+" ");
        }

        sc.close();
    }
}

---

오답노트(푸는 동안 사고과정 및 개선점)

아무 생각 없이 값 찾아서 거기서 for 문 돌려야지 했던 무식한 로직이다. 경계값을 이용하는 방법을 떠올리긴 했으나 구현하기가 너무 어려웠다. 이번 풀이는 몇 번 반복해봐야겠다.

---

정답코드

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main{

    public static int lowerBound(int[] arr, int target){
        int l=0; int r = arr.length;
        while (l<r){
            int m = (l+r)/2;
            if(arr[m]>=target){
                r = m;
            } else{ // 찾았음
                l = m+1;
            }
        }
        return l;
    }

    public static int upperBound(int[] arr, int target){
        int l=0; int r = arr.length;
        while (l<r){
            int m = (l+r)/2;
            if(arr[m]>target){
                r = m;
            } else{ // 찾았음
                l = m+1;
            }
        }
        return l;
    }

    public static void main(String[] args) throws Exception{
        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();
        }
        StringBuilder sb = new StringBuilder();
        Arrays.sort(arr);
        int m = sc.nextInt();
        for(int i=0; i<m;i++){
            int tmp = sc.nextInt();
            sb.append(upperBound(arr,tmp)-lowerBound(arr,tmp)).append(" ");
        }
        System.out.println(sb);

        sc.close();
    }
}

공부하면서 적은 필기를 첨부하겠다.

상한, 하한 경계선을 사용하는 이번 풀이에서는 r = arr.length-1을 해버리면, l을 기준으로 움직이는 반복문이 무한루프에 빠지게 되는 사고가 발생한다.

여담으로 StringBuilder를 안쓰고 그냥 출력했더니 시간초과가 났다. 시간 복잡도 효율성 증가를 위해 뭘 출력할 때는 항상 StringBuilder를 사용하는 습관을 갖자.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^