백준 - 숫자카드2[10816] (이분탐색)

이번 포스팅에서는 백준 알고리즘의 숫자카드2[10816](이분탐색) 코딩테스트 연습 문제를 풀어봅니다.

문제 설명

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

입력 예

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

출력 예

3 0 0 1 2 0 0 2

문제 풀이

둘째 줄의 카드 번호 N에서 동일 요소의 갯수를 카운팅하여 네번째 줄의 M과 동일한 값이 있을경우 카운팅한 숫자를 출력하고 동일한 값이 없으면 0을 출력합니다. 풀이 과정은 아래와 같습니다.

1. 문제의 입력 방식이 여러 줄을 입력 받아 처리함으로 .readline()을 이용하여 여러줄을 입력 받을 수 있도록 처리합니다.
2. 첫번째 줄과 세번째 줄의 값은 연산에 필요하지 않음으로 변수에 저장 하지 않습니다.
3. 두번째 줄과 세번째 줄은 .split()을 이용하여 공백으로 구분되는 값이 각각의 리스트에 저장되게 합니다.
4. 이렇게 얻은 리스트의 string 타입을 map을 이용하여 int로 변환후 다시 맵을 리스트로 변환합니다.
5. try except를 이용하여 N의 리스트 숫자가 countN 딕셔너리에 존재하면 값의 카운트를 증가하고 존재 하지 않으면 딕셔너리에 새로 추가합니다.
6. try except를 이용하여 countN 딕셔너리에 M의 값이 키값으로 존재 하면 해당 값을 출력하고 존재 하지 않으면 0을 출력합니다.

from sys import stdin

# 입력
stdin.readline() # 사용하지 않아서 변수에 저장 하지 않음
N = stdin.readline().split()
stdin.readline()
M = stdin.readline().split()

# string 타입을 map을 이용하여 int로 변환 후 다시 리스트로 변환
N = list(map(int,N))
M = list(map(int,M))

# N에서 동일 요소 카운팅하여 딕셔너리에 저장
countN={}
for i in N:
    try: countN[i] += 1 # 딕셔너리에 숫자가 존재하면 값을 카운트한다.
    except: countN[i] = 1 # 숫자가 존재하지 않으면 딕셔너리에 추가한다.

result = ''
for m in M:
    try: result += str(countN[m]) + ' ' # countN 딕셔너리에 m의 값이 키값으로 존재 하면 해당 값을 출력
    except: result += '0 ' # c존재 하지 않으면 0을 출력
print(result.rstrip())

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
3 0 0 1 2 0 0 2

결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.