[백준] 숫자카드2

문제 

백준 숫자카드 2

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

 

코드

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
want_card = (list(map(int, input().split())))

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1


def binarySearch(arr, target, start, end):
    if start > end:
        return 0

    mid = (start + end) // 2
    if arr[mid] == target:
        return count.get(target)
    elif arr[mid] < target:
        return binarySearch(arr, target, mid + 1, end)
    else:
        return binarySearch(arr, target, start, mid - 1)


for target in want_card:
    print(binarySearch(cards, target, 0, len(cards) - 1), end=" ")

 

풀이

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
want_card = (list(map(int, input().split())))

입력조건에 맞게 선언한다.

이분탐색을 진행할것이기 때문에 cards 배열은 오름차순 정렬한다.

 

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1

count 딕셔너리를 생성한다.

card에 있는 숫자카드들이 몇개 있는지의 정보가 담긴 딕셔너리다.

ex)

card = [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10] 라면

count = {-10: 2, 2: 1, 3: 2, 6: 1, 7: 1, 10: 3} 이다.

 

(여기서부터 순서를 살짝 바꿨다. 코드를 순차적으로 설명하는게 아니라 실행될 함수를 뒤에서 설명한다.)

for target in want_card:
    print(binarySearch(cards, target, 0, len(cards) - 1), end=" ")

원하는 카드를 하나씩 뽑아 해당 카드가 cards배열에 몇개있는지 이분탐색을 한 후 출력한다.

 

def binarySearch(arr, target, start, end):
    if start > end:
        return 0

    mid = (start + end) // 2
    if arr[mid] == target:
        return count.get(target)
    elif arr[mid] < target:
        return binarySearch(arr, target, mid + 1, end)
    else:
        return binarySearch(arr, target, start, mid - 1)

매개변수로

arr은 cards 배열,

target는 for문으로 하나씩 뽑은 원하는 카드,

start와 end는 이분탐색시 사용될 투포인터다.

 

mid는 start와 end의 중간을 가리키는 포인터다.

 

만약 mid가 가리키는곳이 원하는 카드에 해당되면, count 딕셔너리에서 해당 카드의 갯수를 가져온다.

만약 mid가 가리키는곳이 원하는 카드보다 작다면, start 포인터는 mid + 1 로 옮긴다.

만약 mid가 가리키는곳이 원하는 카드보다 크다면, end 포인터는 mid - 1 로 옮긴다.

 

이렇게 start와 end포인터를 옮기며 범위를 좁혀가다가, start와 end 포인터가 교차되면, 이분탐색으로 cards 배열을 모두 탐색해도 원하는 카드가 없다는 뜻이므로, 0을 반환한다.

 

더 나은 코드

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
want_card = list(map(int, input().split()))

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1


for target in want_card:
    print(count.get(target, 0), end=" ")

이분탐색을 사용하지않고, 딕셔너리만 사용하였다. 

 

당연히 실행속도는 더 빠르다.

 

풀이

N = int(input())
cards = sorted(list(map(int, input().split())))
M = int(input())
want_card = list(map(int, input().split()))

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1

앞의 코드와 비교해서 해시(딕셔너리) 생성까지는 똑같다.

 

for target in want_card:
    print(count.get(target, 0), end=" ")

원하는 카드를 하나씩 뽑아 해당 카드가 cards배열에 몇개있는지 get() 함수를 이용하여 출력한다.

만약 원하는 카드가 cards 배열에 없다면, 0을 출력한다.

 

새롭게 배운점 / 느낀점

• dictionary에서 value를 가져올때 인덱스로 키값을 가져올때, 해당 키 값이 없다면, KeyErorr가 난다. get() 함수를 써야지 예외를 발생시키지 않고 키 값에 접근할 수 있다.
  • (딕셔너리).get((키 값), (키가 없을때 리턴할 디폴트 값))
  • 키가 없을때 리턴할 디폴트값을 따로 지정하지 않으면 자동으로 None을 반환한다.
  • ex ) count.get(11, 0) ➡️ count 딕셔너리에 11에 해당하는 키값을 반환한다. 만약 해당 키값이 없다면 0을 반환한다.

 

더 나은 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)