(Python) 백준 10816번 - 숫자 카드 2

 

문제 링크 : https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

풀이

1. lower bound와 upper bound를 사용한 풀이

lower bound와 upper bound를 사용하여 해당 값이 존재하는 위치의 수를 계산하는 방식으로 문제 풀이를 진행했다. 

import sys

def lower(arr, num): # lower bound : 해당 값이 처음으로 나타나는 인덱스 반환
    low, high = 0, len(arr)
    while low < high:
        mid = (low+high)//2
        if num <= arr[mid]: # 해당 값이 현재 위치보다 작거나 같다면, high를 현재 인덱스로 변경 
            high = mid
        else: # 그렇지 않다면, low를 현재 위치보다 1씩 크게 조절 
            low = mid + 1
    return high

def upper(arr, num): # upper bound : 해당 값보다 큰 값이 처음으로 나타나는 인덱스 반환
    low, high = 0, len(arr)
    while low < high:
        mid = (low+high)//2
        if num < arr[mid]: # 해당 값이 현재 위치보다 작거나 같다면, high를 현재 인덱스로 변경 
            high = mid
        else: # 그렇지 않다면, low를 현재 인덱스보다 1씩 크게 조절 
            low = mid + 1 
    return high

n = int(sys.stdin.readline())
arr = sorted(list(map(int, sys.stdin.readline().split())))
n = int(sys.stdin.readline()) # n을 사용하지 않아서 덮어써도 됨
find_arr = list(map(int, sys.stdin.readline().split())) # 배열에서 찾을 값들
for i in find_arr:
    print(upper(arr, i) - lower(arr, i), end=' ') # 값들의 개수는 upper bound - lower bound

 

2. dictionary를 사용한 풀이

dictionary에 해당 값과 값이 등장하는 수를 계산한 뒤 이를 반환하는 형식으로 문제 풀이를 진행했다.

import sys

ndic = {} # dictionary
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
for i in arr: # dicionary에 특정 값과 그 값의 등장 횟수 저장
    if i in ndic: # dictionary에 이미 존재하는 key면
        ndic[i] += 1 # 등장 개수 증가
    else: # dictionary에 존재하지 않는 key라면
        ndic[i] = 1 # 1 저장
n = int(sys.stdin.readline()) # n은 사용하지 않으므로 덮어써도 됨
arr = list(map(int, sys.stdin.readline().split())) # 이전 arr는 사용하지 않으므로 덮어써도 됨
for i in arr: # arr 순회하며
    if i in ndic: # dictionary에 존재하면
        print(ndic[i], end=' ') # 등장 횟수 반환
    else: # 없다면
        print(0, end=' ') # 0 반환