숫자 카드 2 [ Python ] [ 백준 : 10816 ]

---

풀이 및 회고

 

이분 탐색 문제가 재밌어서 하나 더 풀어보았다. 앞서 했던 수 찾기 문제처럼 풀려고 접근했으나 구현이 어려워졌다.

첫번째가 실패라고 생각하여 코드를 수정하고 다시 진행했다. 예제처럼 정답이 나왔으나 제출했더니 틀렸습니다 가 나왔다.

예제와 다른 케이스인 10 10 9 -5 2 3 4 5 를 넣어보니 어디가 잘못되었는지 찾을 수 있었다.

조건을 추가해주었고 문제없이 잘 작동하는 모습을 보니 너무 뿌듯했다.

하지만 다른 분들이 푼 코드를 보니 비슷한 방식으로 푼 사람이 별로 없었고, 대부분 Counter 를 사용해서 문제를 풀었다.

이분 탐색에 너무 꽂혀있어 다른 방법을 생각하지 못했던 것 같다.

또 내가 처음에 포기한 방식으로도 방법을 찾아내 문제를 푼 사람도 있었다. 조금만 더 생각해볼걸 하는 아쉬움이 있었다.

# 숫자 카드 2

#알고리즘

# 1트 실패=====================
#1. n을 입력받는다
# #1, n만큼 숫자를 입력받아서 A에 저장한다.
# #1. n_list 를 정렬한다.
# n = int(input())
# n_list = list(map(int, input().split()))
# n_list.sort()
# #2. m을 입력받는다
# #2, m만큼 숫자를 입력받아서 B에 저장한다.
# m = int(input())
# m_list = list(map(int, input().split()))
# answer = []
# #2. m_list의 원소들을 꺼내면서 다음과 같은 과정을 수행한다.
# for m_list_index in m_list:
#     #3. cnt 를 0으로 설정한다.
#     cnt = 0
#     #3. start,end을 설정한다. 각각 0, n-1이라고 설정한다.
#     start, end = 0, n - 1
#     #4. start가 end보다 작을때까지 반복한다.
#     while start <= end:
#         #4. (1) middle 를 다음과 같이 설정한다.-> middle = start + end // 2
        
#         middle = (start + end) // 2
#         if n_list[middle] == m_list_index:
#             cnt += 1
#             print(start, end, cnt)
#         elif n_list[middle] < m_list_index:
#             start = middle + 1
#         else:
#             end = middle - 1
#     print(middle)
#     answer.append(cnt)
# print(answer)

# #4. (2) n_list[middle] == B의 각 원소
#     # cnt += 1
# #4. (3) A[middle] < b의 각 원소
#     # start = middle + 1
# #4. (4) A[middle] > b의 각 원소
#     # end = midlle - 1
# #5. while문을 통과하고 cnt를 answer에 추가한다.

# 2트 실패 ============================
# N = int(input())
# N_list = list(map(int, input().split()))
# N_list.sort()
# M = int(input())
# M_list = list(map(int, input().split()))
# index = 0
# answer = {}
# for mIndex in sorted(M_list):
#     cnt = 0
#     while index < len(N_list):
#         if N_list[index] == mIndex:
#             cnt += 1
#             index += 1
#         elif N_list[index] < mIndex:
#             index += 1
#         else:
#             break
#     answer[mIndex] = cnt
# print(' '.join(str(answer[mIndex]) for mIndex in M_list))
# index = 0
#M_list 에 있는 원소들을 하나씩 살피면서 다음과정을 실행한다. 
#1. index < N_list 까지 다음 과정을 반복한다.
#1. (1) cnt = 0으로 초기화를 해준다.
#1, (2) N_list[index] == m : cnt += 1 index += 1
#2. (3) N_list[index] < m : index += 1
#3. (4) N_list[index] > m : break
#4. while 반복문을 나가고 나서 answer에 cnt를 추가해준다.

# [1,2,3,4,5,6,7,8,9,10,11]
# [3,4,5,6,7,8,9,10,10,10,11,12,13]
# {-10: 2, -5: 0, 2: 1, 3: 2, 4: 0, 5: 0, 9: 0, 10: 3}


# 3트 시도 =====================
import sys

N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))
N_list.sort()
M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))
index = 0
answer = {}
for mIndex in sorted(M_list):
    cnt = 0
    if mIndex not in answer:
        while index < len(N_list):
            if N_list[index] == mIndex:
                cnt += 1
                index += 1
            elif N_list[index] < mIndex:
                index += 1
            else:
                break
        answer[mIndex] = cnt
print(' '.join(str(answer[mIndex]) for mIndex in M_list))

# 다른사람이 Counter 로 푼 코드======================
# import sys
# from collections import Counter

# n = int(sys.stdin.readline())
# cards = Counter(list(map(int, sys.stdin.readline().split())))

# m = int(sys.stdin.readline())
# numbers = list(map(int, sys.stdin.readline().split()))
# for i in numbers:
#     print(cards[i], end = ' ')


# 내가 포기했던 방식으로 다른사람이 푼 코드 =======================
# import sys
# input = sys.stdin.readline

# N = int(input())
# array = sorted(list(map(int, input().split())))
# M = int(input())
# target_array = list(map(int, input().split()))

# def binaryF(array, target, start, end):
#     cnt = 0
#     while start <= end:
#         mid = (start+end)//2
#         if array[mid] == target:
#             for i in range(start, end+1):
#                 if array[i] == target:
#                     cnt += 1
#             return cnt
#         elif array[mid] < target:
#             start = mid + 1
#         else:
#             end = mid - 1
#     return 0        
    
# d = {}
# for m in target_array:
#     if m not in d:
#         d[m] = binaryF(array,m,0,N-1)
#     print(str(d[m]), end = ' ')