백준_단계별로 풀어보기_14단계_집합과 맵

몽골 여행을 다녀왔다. 그래서 블로그를 오래 비웠다. 이제 다시 시작!

그리고 왜 11단계 다음에 14단계냐면 그전 단계는 자료구조라 아직 건들지 않았다.

이제 슬슬 자료구조 다시 공부하며 풀어나갈 예정

---

■ 백준 10815 숫자카드_실버 5

#최초코드: 684 ms
# n = input()
# card = set(list(map(int, input().split())))
# m = input()
# bool_card = list(map(int, input().split()))
# for i in bool_card:
#     print(1 if i in card else 0, end=" ")

#최종코드: 444 ms
import sys
n = sys.stdin.readline()
card = set(sys.stdin.readline().split())
m = sys.stdin.readline()
bool_card = sys.stdin.readline().split()
print("".join("1 " if i in card else "0 " for i in bool_card))

# #고수코드: 입력이 한번에 들어오므로 입력 개수를 상관하지 않는
# # 파이썬 특성을 이용해 1,3번째 입력은 생략했다.
# # 신기한게 A, B는 리스트를 취하지 않았음에도 불구하고 리스트의 형태를 띄고 있다.
# # [(복습)포인트]
# # 1) string을 split하면 list의 형태를 띄게 된다.
# # 2) 숫자라고 하고 숫자로 저장할 필욘없다. 연산이 아니라 대조이면 더더욱
# # 3) join은 빠르다
# # 4) set은 해쉬를 쓰므로 O(1)이다
# import sys
# A, B = sys.stdin.read().split("\n")[1::2]
# A = set(A.split())
# B = B.split()
# print("".join("1 " if x in A else "0 " for x in B))

 

■ 백준 14425 문자열 집합_실버 3

import sys
n, m = map(int, input().split())
s = []
cnt = 0
for i in range(n):
    s.append(sys.stdin.readline().rstrip())
s = set(s)
for j in range(m):
    if sys.stdin.readline().rstrip() in s:
        cnt += 1
print(cnt)

# #고수코드: 입력을 한 번에 받고, A를 슬라이싱하여 사용
# N,S,*A=open(0).read().split();N=int(N)
# K={*A[:N]}
# print(sum(i in K for i in A[N:]))

 

■ 백준 7785 회사에 있는 사람_실버 5

import sys
firm = dict()
for i in range(int(input())):
    name, enter_log = sys.stdin.readline().split()
    firm[name] = enter_log
for k,v in sorted(firm.items(), reverse=True):
    if v == "enter": print(k)

# #고수코드: bool과 join을 활용하도록 하자
# import sys
# res = {}
# for i in range(int(input())):
#     a, b = sys.stdin.readline().split()
#     if b == 'enter': res[a] = 1
#     else: del res[a]
# print('\n'.join(sorted(res.keys(),reverse=True)))

 

■ 백준 1620 나는야 포켓몬 마스터 이다솜_실버 4

#최초코드
N, M, *A = open(0).read().split();N=int(N)
k = {v:i+1 for i,v in enumerate(A[:N])}
k_idx = {i+1:v for i,v in enumerate(A[:N])}
for i in A[N:]:
    print(k_idx[int(i)] if i.isnumeric() else k[i])

#최종코드
N, M, *A = open(0).read().split();N=int(N)
k = {v:str(i+1) for i,v in enumerate(A[:N])}
print("\n".join(A[int(i)-1] if i.isnumeric() else k[i] for i in A[N:]))

# #고수코드: index가 있으면 그냥 리스트를 이용해도 좋다! 괜히 dict 하나 더 만들었네
# import sys
# lines = sys.stdin.buffer.read().decode().splitlines()
# n, m = map(int, lines[0].split())
# dic = {word: str(idx + 1) for idx, word in enumerate(lines[1:n + 1])}
# answer = '\n'.join(lines[int(line)] if line.isdigit() else dic[line] for line in lines[1 + n:])
# print(answer)

 

■ 백준 10816 숫자 카드 2_실버 4 (복습)

# (복습)
# 최초코드: 2152 ms
# import sys
# import bisect
# card, cnt_card = sys.stdin.read().split("\n")[1::2]
# card = sorted(card.split())
# cnt_card = cnt_card.split()
# for i in cnt_card:
#     print(bisect.bisect_right(card, i) - bisect.bisect_left(card, i), end=" ")

# #최종코드: 508 ms / 하나하나 print 하는 것 보다 모아서 join하는게 더 빠르다
# import sys
# card, cnt_card = sys.stdin.read().split("\n")[1::2]
# card = card.split()
# cnt_card = cnt_card.split()
# dict_card = dict()
# res = []
# for i in card:
#     if i in dict_card:
#         dict_card[i] += 1
#     else:
#         dict_card[i] = 1
# for j in cnt_card:
#     res.append(dict_card.get(j, 0))
# sys.stdout.write(' '.join(str(r) for r in res))

# 고수코드: 요소의 개수를 value로 딕셔너리에 넣고 get 사용하여 해당 key의 value(개수) 리턴
# dict.get(key, "no"): dict에 key가 있다면 그 value값 반환, 없다면 "no" 반환
import sys
input = sys.stdin.readline
res = []
input()
x = dict()
for num in input().split():
    if num in x:
        x[num]+=1
    else:
        x[num] = 1
print(x)
input()
for n in input().split():
    res.append(x.get(n,0))
sys.stdout.write('\n'.join([str(r) if r else '0' for r in res]))

 

■ 백준 1764 듣보잡_실버 4

N, M, *A = open(0).read().split(); N=int(N)
subset = sorted(set(A[:N]) & set(A[N:]))
print(len(subset))
print("\n".join(subset))

 

■ 백준 1269 대칭 차집합_실버 4

# import sys
# A, B = sys.stdin.read().split("\n")[1:3]
# print(len({*A.split()}^{*B.split()}))

#고수코드: set 연산을 쓰지 않았다.
a,b,c=open(0)
a=(b+c).split()
print(2*len({*a})-len(a))

 

■ 백준 11478 서로 다른 부분 문자열의 개수_실버 3 (복습)

# set은 해시맵으로 구현되어, 해시 충동이 일어날 경우 worst case는 O(N)이다.
# 최초 코드는 모든 길이의 subset을 하나의 해시맵에 넣어 해시 충돌이 일어날 가능성이 크고
# 고수 코드는 길이별로 subset을 따로 세기 때문에 해시 충돌이 일어날 가능성이 더 낮다.
# # 최초 코드: 508ms
# s = input()
# subset = set()
# for i in range(1, len(s)+1):
#     for j in range(len(s)-i+1):
#         subset.add(s[j:j+i])
# print(len(subset))

# 최종 코드: 256ms
s = input()
ans = 0
for i in range(1, len(s)+1):
    subset = set()
    for j in range(len(s)-i+1):
        subset.add(s[j:j+i])
    ans += len(subset)
print(ans)

# # 고수코드: 200ms
# def substring(s, l):
#     subs = set()
#     for i in range(len(s)-(l-1)):
#         subs.add(s[i:i+l])
#     return subs
#
# word = input()
# substrs=0
# for i in range(len(word)):
#     substrs+=len(substring(word, i+1))
# print(substrs)