[ baekjoon ] 10816. 숫자 카드 2

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 : 순서대로 카드 세기

import sys
input = sys.stdin.readline

n = int(input())
cards = sorted(list(map(int, input().split())))

m = int(input())
sols = list(map(int, input().split()))

dict_sols = {}

idx = 0
for sol in sorted(sols):
  cnt = 0
  if sol not in dict_sols: # 이 조건 없으면 틀림
    while idx < n:
      if cards[idx] == sol:
        cnt += 1
        idx += 1
      elif cards[idx] < sol:
        idx += 1
      else:
        break
    dict_sols[sol] = cnt
  
print(' '.join(str(dict_sols[i]) for i in sols))

주어진 n개의 숫자 카드(cards)와, 구해야 할 숫자 카드(sols) 번호 두개를 모두 정렬한 채로 계산한다.
다만 sols는 출력할 때, 순서를 알아야 하므로,
for sol in sorted(sols)처럼 하나의 배열을 반환하게 한다.
idx로 cards의 인덱스를 하나씩 늘린다. 만약 카드번호 sol과 같다면, cnt와 idx에 1을 더한다(cnt : 카드번호 sol의 개수, idx : cards의 다음 카드를 탐색)
만약 sol이 더 작다면, 더이상 sol에 해당하는 카드가 존재하지 않으므로 while문을 종료한다.
이때 주의할 점은 if sol not in dict_sols 조건을 확인해야한다 !!
(이거 업스면,, 1%에서 탈락)

마지막 출력하는 것은 정렬이 안된, raw 상태인 cards 배열에서 for문을 돌려 출력한다.
join 함수 알도록 !

문자열 일정 길이로 자르기
s : 문자열, length : 문자열 길이, i : 자를 길이 단위
arr = [s[j:j+i] for j in range(0, length, i)]
arr = list(map(''.join, zip([iter(s)] i)))

소스코드 2 : 해시 알고리즘

import sys
input = sys.stdin.readline

n = int(input())
cards = list(map(int, input().split()))

m = int(input())
sols = list(map(int, input().split()))

hashmap = {}

for card in cards:
  if card in hashmap:
    hashmap[card] += 1
  else:
    hashmap[card] = 1

print(' '.join(str(hashmap[i]) if i in hashmap else '0' for i in sols))

해시 자료구조는 dictionary 라이브러리를 많이 사용한다고 함.
hashmap 딕셔너리를 선언해서,
cards 에 있는 카드들을 딕셔너리에 모두 추가시킨다.

for card in cards:
  if card in hashmap:
    hashmap[card] += 1
  else:
    hashmap[card] = 1

이 for문을 모두 반복하면 cards의 모든 카드들의 숫자가 세어져 있다.

그 후, 우리가 구해야할 카드가 있는 sols로 for문을 돌려 출력하면 된다.
join 공부하자.. else 없으면 syntax error

이진 탐색으로 알고리즘이 분류되어있지만,, 나는 전혀 못 떠올릴 것 같아서 다른 방법을 찾아봤다. 그래도 이진탐색으로 푼 소스코드도 봐야지

소스코드 3 : 이진탐색

(시간 가장 오래걸림)

import sys
input = sys.stdin.readline

n = int(input())
cards = sorted(list(map(int, input().split())))

m = int(input())
sols = list(map(int, input().split()))


dict_sols = {}

def binary_search_recur(num, arr, start, end):
  if start > end: return 0
  mid = (start + end) // 2
  if num == arr[mid]:
    return arr[start:end+1].count(num)
  elif num < arr[mid]:
    return binary_search_recur(num, arr, start, mid - 1)
  else:
    return binary_search_recur(num, arr, mid + 1, end)

for card in cards:
  if card not in dict_sols:
    dict_sols[card] = binary_search_recur(card, cards, 0, n - 1)

print(' '.join(str(dict_sols[i]) if i in dict_sols else '0' for i in sols))

이진 탐색을 하기 위해 정렬된 cards를 저장
이진 탐색에서 cards 배열의 카드(card)를 모두 탐색한다.
num == arr[mid](중간값)일 때 : start에서 end까지의 범위에서 count()로 num의 개수를 count
크거나 작으면 : 재귀 함수 호출