백준 10816 숫자 카드 2

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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 

10

6 3 2 10 10 10 -10 -10 7 3

8

10 9 -5 2 3 4 5 -10

예제 출력 1 

3 0 0 1 2 0 0 2

---

[풀이 과정]

1. 주어진 형식에 따라 입력을 받는다.

 

2. 이분탐색을 활용하기 위해 arr1을 오름차순으로 정렬한다. 

 

3. 중복된 갯수를 미리 딕셔너리를 사용해서 처리한다.

- arr1을 순회하면서 딕셔너리에 아직 값이 없으면 key는 해당 값, value는 1로 저장한다.

- arr1을 순회하면서 딕셔너리에 이미 있으면 해당 key의 value를 1증가시킨다.

 

4. arr2를 순회하면서 각 값마다 이분탐색으로 arr1에 존재하는지 확인한다.

- res == 1 이면 값이 arr1에 존재하는 것이기 때문에 딕셔너리에 저장해놓았던 갯수를 출력한다.

- res == -1이면 값이 arr1에 존재하지 않는 것이기 때문에 0을 출력한다.

---

[소스 코드]

def find(target, start, end):
    while start <= end:
        mid = (start+end)//2
        if arr1[mid] == target:
            return 1
        elif arr1[mid] < target:
            start = mid+1
        elif arr1[mid] > target:
            end = mid-1
    return -1

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

arr1.sort()
dict1 = {}

for i in arr1:
    if i not in dict1:
        dict1[i] = 1
    else:
        dict1[i] += 1

for i in arr2:
    res = find(i, 0, len(arr1)-1)
    if res == 1:
        print(dict1[i], end=' ')
    else:
        print(0, end=' ')

 

https://github.com/chojaehyo/CodingTest/blob/main/%5BBOJ%5D%EC%88%AB%EC%9E%90%20%EC%B9%B4%EB%93%9C%202_%20python

GitHub - chojaehyo/CodingTest