코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67
문제
https://www.acmicpc.net/problem/10816
[나의 풀이]
import java.util.Arrays;
import java.util.Scanner;
public class Try2 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
int N = stdIn.nextInt();
int [] cardArray = new int[N];
for (int i=0;i<N;i++){
cardArray[i] = stdIn.nextInt();
}
Arrays.sort(cardArray);
int M = stdIn.nextInt();
int [] findArray = new int[M];
for (int i=0;i<M;i++){
findArray[i] = stdIn.nextInt();
}
for (int i : binary_search(cardArray, findArray)){
System.out.print(i+" ");
}
}
private static int [] binary_search(int [] cardArray, int [] findArray){
int [] output = new int [findArray.length];
for (int i=0;i<findArray.length;i++){
int pl = 0;
int pc = cardArray.length/2;
int pr = cardArray.length-1;
while(findArray[i]!=cardArray[pc]){
if(findArray[i]>cardArray[pc]){
pl = pc+1;
pc += (pr-pl)/2+1;
}
else{
pr = pc-1;
pc = pc-(pr-pl)/2-1;
}
if(pl > pc || pc > pr){
break;
}
}
if ( 0<=pc && pc < cardArray.length && findArray[i]==cardArray[pc]){
output[i] +=1;
for (int m=pc-1; 0<=m;m--){
if (cardArray[m]==findArray[i]){
output[i] +=1;
}
}
for (int m=pc+1; m<=pr;m++){
if (cardArray[m]==findArray[i]){
output[i] +=1;
}
}
}
}
return output;
}
}
[정답 풀이]
import java.util.Arrays;
import java.util.Scanner;
public class Correct_answer {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for(int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr); // 이분 탐색을 하기 위해서는 반드시 정렬되어있어야 한다.
int M = in.nextInt();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {
int key = in.nextInt();
// upperBound와 lowerBound의 차이 값을 구한다.
sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
}
System.out.println(sb);
}
private 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;
}
private 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;
}
}
나의 풀이는 이진 탐색을 사용했음에도 계속 시간초과가 났다. 그리하여 정답을 참고하였고 Upperbound와 Lowerbound 개념을 활용해서 푼 것을 확인할 수 있었다.