[12단계] 집합과 맵

10815번. 숫자카드

 

▼해설보기

1. 이진탐색 알고리즘

import sys

n = int(sys.stdin.readline())
number_cards = list(map(int, sys.stdin.readline().split())) # 상근이가 가지고 있는 숫자 카드 입력
number_cards.sort() # 이진탐색을 위한 오름차순 정렬
m = int(sys.stdin.readline())
target_numbers = list(map(int, sys.stdin.readline().split())) # 판별해야하는 숫자카드 입력

# 이진탐색을 통해 해당 숫자가 존재하는지 확인한다.
# 이진탐색 알고리즘 짜는 걸 연습하기 위해 해당 방법을 사용

# 타겟 숫자를 하나씩 뽑아서 상근이가 가지고 있는 숫자 카드에 있는 지 확인한다.
for target in target_numbers:
    start = 0 # 첫 인덱스
    end = n - 1 # 마지막 인덱스

    while True:
        mid = (end + start) // 2
        # start가 end보다 커질 경우 0을 출력하고 이를 종료한다.
        if start > end:
            print(0, end=' ')
            break
        # 상근이가 가지고 있는 카드의 중간 값이 target보다 클 경우 왼쪽을 탐색한다.
        elif number_cards[mid] > target:
            end = mid-1
        # 상근이가 가지고 있는 카드의 중간 값이 target보다 작을 경우 오른쪽을 탐색한다.
        elif number_cards[mid] < target:
            start = mid+1
        # 상근이가 가지고 있는 카드의 중간 값이 target과 같을 경우 탐색을 종료하고 1을 출력한다.
        elif number_cards[mid] == target:
            print(1, end=' ')
            break

 

2. 해쉬함수 set 이용

# set 자료구조를 사용한다.
# set 자료구조는 해쉬값을 사용하기때문에 O(1)이 나온다.
import sys

n = int(sys.stdin.readline())
num_cards = set(map(int, sys.stdin.readline().split())) # 상근이가 가지고 있는 숫자 카드 입력
m = int(sys.stdin.readline())
target_nums = list(map(int, sys.stdin.readline().split())) # 판별해야하는 숫자카드 입력

for target in target_nums:
    if target in num_cards:
        print(1, end=' ')
    else:
        print(0, end=' ')

 

---

14425번. 문자열 집합

 

▼해설보기

import sys
input = sys.stdin.readline
n, m = map(int,input().split())

s = set()
for i in range(n) :
    i = input()
    s.add(i)
cnt = 0
for _ in range(m):
    j = input( )
    if j in s:
        cnt += 1
print(cnt)

set과 dict는 hash 구조(key에 데이터를 저장하는 구조, key를 통해 데이터를 받아오기 때문에 빠름)를 사용한다.

(set은 key만 있고, dict는 key와 value가 있음)

hash는 hashing function(key에 대한 산술 연산을 통해 데이터의 위치를 찾는 함수)을 이용하기 때문에 O(1)에서 최악의 경우 O(n)의 시간 복잡도를 갖는다.

---

10816번. 숫자카드2

 

 

▼해설보기

 

import sys
input = sys.stdin.readline

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

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

for target in candidate:
    result = count.get(target)
    if result == None:
        print(0, end=" ")
    else:
        print(result, end=" ")

---

1764번. 듣보잡

 

 

▼해설보기

n, m =map(int,input().split())

a=set()
for i in range(n):
    a.add(input())

b=set()
for i in range(m):
    b.add(input())

result = sorted(list(a & b))

print(len(result))

for i in result:
    print(i)

 

---

1269번. 대칭차집합

 

 

▼해설보기

n, m = map(int, input().split())
a = set(map(int, input().split()))
b = set(map(int, input().split()))
print(len(a-b)+len(b-a))

---

11478번. 서로 다른 부분 문자열의 개수

 

 

▼해설보기

n = input()
num = set()

for i in range(len(n)):
    for j in range(i, len(n)):
        temp = n[i : j+1]
        num.add(temp)
print(len(num))