본문 바로가기
알고리즘/백준

백준 10816 숫자 카드 2 (HashMap과 BinarySearch를 이용한 풀이)

by Renechoi 2023. 7. 4.

백준 10816 숫자 카드 2 (JAVA 자바 풀이)

 

 

 

📌 문제 

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

 

📣 출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

 

 

 

 

 

1. HashMap 풀이

 

HashMap 특성을 이용해서 푼다. 

 

카드의 값을 Key로 사용하고, 카드의 개수를 Value로 저장한다.

만약 이미 HashMap에 해당 카드가 존재한다면, 해당 카드의 Value에 1을 더해준다.

 

2. BinarySearch 풀이 

 

해쉬맵을 사용하면 쉽게 풀리지만 직접 바이너리 서치를 구현해보기 좋은 문제이다. 

 

바이너리 서치는 기본적으로 있는 값을 찾도록 한다. 

 

그렇다면 그 값이 여러 개인 경우는 어떻게 알 것인가? 두가지 방법이 있다. 우선 중복된 값 모두 바이너리 서치의 배열로 들어오는 인자값들이 정렬이 되어있는 특성을 이용한다. 

 

 

1) 카운트 변수로 중복값 찾기 -> 실패 

첫 번째 방법은 카운트 변수를 통해 중복 값을 찾는 것이다. 

 

다른 경우와 마찬가지로 count 변수를 사용하여 해당 값이 있는 경우라면 옆에 것을 탐색하여 카운트를 올려주고 이를 숫자 값이 달라질 때까지 돌린다. 

 

코드 구현은 다음과 같다. 

 


public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {

      int N = Integer.parseInt(bufferedReader.readLine());
      int[] numbers = new int[N];

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      while (N-->0){
         numbers[N] = Integer.parseInt(stringTokenizer.nextToken());
      }

      Arrays.sort(numbers);

      int M = Integer.parseInt(bufferedReader.readLine());
      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      StringBuilder stringBuilder = new StringBuilder();
      while (M-->0){
         int count = binarySearch(Integer.parseInt(stringTokenizer.nextToken()), numbers);
         stringBuilder.append(count).append(" ");
      }
      System.out.println(stringBuilder);
   }

   private static int binarySearch(int number, int[] numbers){
      int left = 0;
      int right = numbers.length-1;
      int count =0;

      while (left<=right){
         int mid = (left+right)/2;
         if(number<numbers[mid]){
            right = mid-1;
            continue;
         }
         if (number > numbers[mid]){
            left = mid+1;
            continue;
         }
         if (number==numbers[mid]){
            count++;
            while(true){
               if (mid==numbers.length-1){
                  break;
               }
               if(number==numbers[++mid]){
                  count++;
               } else{
                  break;
               }
            }
         }
         break;
      }
      return count;
   }
}

 

 

 

이 경우 대부분의 경우에 대해 맞지만 다음과 같이 절반 이상이 동일 값으로 주어지면 해를 찾지 못한다. 

 

5
1 1 1 1 1
1
1

 

 

그 이유는 바이너리 서치의 특성상 처음 1회부터 반으로 쪼개는데, 이때 나머지 영역의 값들은 버려지기 때문이다. 하지만 실제로는 적합해들이 반대편에도 있기 때문에 이 역시도 계수해주어야 한다. 

 

 

2) 범위를 지정해 찾기 : LowerBound, UpperBound 이용 -> 성공 

 

찾고자하는 값 x에 대해서 해당 값이 처음 나타나는 위치와 마지막 나타나는 위치를 각각 구해준다. 

 

이때 위치를 찾은 다음에 최종 위치를 갱신해가면서 가장 낮거나 가장 높은 인덱스를 찾아야 한다. 따라서 찾고자 하는 값을 찾았을 때 반복문을 종료하는 일반 바이너리서치와는 다르게 계속해서 탐색을 이어간다.

 

private static int findLowerBoundIdx(int number, int[] numbers){
   int left = 0;
   int right = numbers.length-1;
   int index =numbers.length;

   while (left<=right){
      int mid = (left+right)/2;
      if (numbers[mid]<number){
         left = mid +1;
      } else {
         right = mid -1;
         index = mid;
      }
   }
   return index;
}

 

upper를 지정할 때는 등호를 포함한다. lower에서는 찾은 값과 찾고자 하는 값이 크거나 같을 때 계속해서 작아진다. upper bound의 경우에는 찾은 값이 찾고자 하는 값보다 클 때만 커져야 한다. 

 

lower는 해당 값을 포함한 index이지만, upper는 찾고자 하는 값 X에 대해 초과인 index여야 하기 때문이다. 

 

 


private static int findUpperBoundIdx(int number, int[] numbers){
   int left = 0;
   int right = numbers.length-1;
   int index = numbers.length;

   while (left<=right){
      int mid = (left+right)/2;
      if (numbers[mid] <= number){
         left = mid +1;
      } else {
         right = mid -1;
         index = mid;
      }
   }
   return index;
}

 

 

그런데 생각해보면 index 변수 값을 사용하지 않고 left와 right가 index의 값을 가지도록 할 수도 있다. 

 

경계값을 다음과 같이 설정해서 개구간과 폐구간이냐에 따라 달라지도록 한다. 

 

private static int findLowerBoundIdx(int number, int[] numbers){
   int left = 0;
   int right = numbers.length;

   while (left<=right){
      int mid = (left+right)/2;
      if (numbers[mid]<number){
         left = mid +1;
      } else {
         right = mid;
      }
   }
   return left;
}

 

 

 

 

💡 코드 구현

 

 

 

HashMap을 이용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		int numberOfCards = Integer.parseInt(bufferedReader.readLine());

		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		HashMap<Integer, Integer> cards = new HashMap<>();
		for (int i = 0; i < numberOfCards; i++) {
			int card = Integer.parseInt(stringTokenizer.nextToken());
			cards.put(card, cards.getOrDefault(card, 0) + 1);
		}

		int testCases = Integer.parseInt(bufferedReader.readLine());
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		StringBuilder stringBuilder = new StringBuilder();
		for (int i = 0; i < testCases; i++) {
			int query = Integer.parseInt(stringTokenizer.nextToken());
			stringBuilder.append(cards.getOrDefault(query, 0)).append(" ");
		}
		System.out.println(stringBuilder);
	}
}

 

 

 

 

BinarySearch를 이용한 풀이 

 

 


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {

      int N = Integer.parseInt(bufferedReader.readLine());
      int[] numbers = new int[N];

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      while (N-->0){
         numbers[N] = Integer.parseInt(stringTokenizer.nextToken());
      }

      Arrays.sort(numbers);

      int M = Integer.parseInt(bufferedReader.readLine());
      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      StringBuilder stringBuilder = new StringBuilder();
      while (M-->0){
         int value = Integer.parseInt(stringTokenizer.nextToken());
         int lowerBoundIdx = findLowerBoundIdx(value, numbers);
         int upperBoundIdx = findUpperBoundIdx(value, numbers);
         stringBuilder.append(upperBoundIdx-lowerBoundIdx).append(" ");
      }
      System.out.println(stringBuilder);
   }

   private static int findLowerBoundIdx(int number, int[] numbers){
      int left = 0;
      int right = numbers.length;

      while (left<=right){
         int mid = (left+right)/2;
         if (numbers[mid]<number){
            left = mid +1;
         } else {
            right = mid;
         }
      }
      return left;
   }

   private static int findUpperBoundIdx(int number, int[] numbers){
      int left = 0;
      int right = numbers.length-1;
      int index = numbers.length;

      while (left<=right){
         int mid = (left+right)/2;
         if (numbers[mid] <= number){
            left = mid +1;
         } else {
            right = mid -1;
            index = mid;
         }
      }
      return index;
   }
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

백준 1654 랜선 자르기(JAVA 자바 풀이)  (0) 2023.12.25
백준 2805 나무 자르기 (JAVA 자바 풀이)  (1) 2023.12.25
백준 2470 두 용액 (JAVA 자바 풀이: 이분 탐색 활용)  (0) 2023.07.04
백준 2295 세 수의 합 (JAVA 자바 풀이)  (1) 2023.07.04
백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이)  (0) 2023.07.03

관련글

티스토리툴바