[백준 10816] 숫자 카드 2 (java)

[백준 10816] 숫자 카드 2 (java)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ_숫자카드2_10816 { public static void main( String [] args) throws Exception { BufferedReader br = new BufferedReader( new InputStreamReader( System . in )); StringTokenizer st; int N = Integer. parseInt (br.readLine()); int [] arr = new int [N]; st = new StringTokenizer(br.readLine()); for ( int i = 0 ; i < N; i + + ) { arr[i] = Integer. parseInt (st.nextToken()); } Arrays.sort(arr); // 항상 이분탐색할 때 중요!!!!! int M = Integer. parseInt (br.readLine()); st = new StringTokenizer(br.readLine()); StringBuilder sb = new StringBuilder(); for ( int i = 0 ; i < M; i + + ) { int m = Integer. parseInt (st.nextToken()); sb.append(upperBound(arr,m) - lowerBound(arr,m)).append( " " ); } System . out . println (sb. toString ()); } static int lowerBound( int [] arr, int key) { int lo = 0 ; int hi = arr. length ; // lo가 hi랑 같아질 때까지 반복 while (lo < hi) { int mid = (lo + hi) / 2 ; // 중간위치를 구한다. /* * key 값이 중간 위치의 값보다 작거나 같을 경우 * * 중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다. */ if (key < = arr[mid]) { hi = mid; } else { lo = mid + 1 ; } } return lo; } static int upperBound( int [] arr, int key) { int lo = 0 ; int hi = arr. length ; // lo가 hi랑 같아질 때 까지 반복 while (lo < hi) { int mid = (lo + hi) / 2 ; // 중간위치를 구한다. // key값이 중간 위치의 값보다 작을 경우 if (key < arr[mid]) { hi = mid; } // 중복원소의 경우 else에서 처리된다. else { lo = mid + 1 ; } } return lo; } } Colored by Color Scripter

from http://yeonobly.tistory.com/66 by ccl(A) rewrite - 2021-11-18 19:02:00