★Set/Map Intermediate I - 13 Solved★

★ 1620 나는야 포켓몬 마스터 이다솜 ★

 

import sys
input=sys.stdin.readline

pokemon={}
N,M=map(int,input().strip().split())

for i in range(N):
    pokemon[input().strip()]=i+1

pokemon_list=list(pokemon.keys())

for _ in range(M):
    problem=input().strip()
    if problem.isalpha():print(pokemon[problem])
    else:print(pokemon_list[int(problem)-1])

 

😽 포켓몬 번호를 말하면 포켓몬 이름을 출력하고, 반대로 포켓몬 이름을 말하면 포켓몬 번호를 출력하는, 즉 두 가지 정보 포켓몬 번호와 포켓몬 이름을 저장하고, 많은 정보가 들어가도 searching하는 데 효율적인 자료구조 hash-table을 사용하면 된다.

 

😽 hash-table searching연산

① pokemon[problem]으로, 포켓몬 이름인 key에 해당하는 포켓몬 번호 value 출력 O(1)

② pokemon의 keys를 list로 만들고, list의 indexing으로 포켓몬 이름 key 출력 O(1)

---

★ 1764 듣보잡 ★

 

import sys
input=sys.stdin.readline

not_listened=set()

N,M=map(int,input().split())

total=0
ans=[]

for _ in range(N):
    not_listened.add(input().rstrip())

for _ in range(M):
    not_seen_name=input().rstrip()
    if not_seen_name in not_listened:
        total+=1
        ans.append(not_seen_name)
print(total)
ans.sort()
print(*ans,sep='\n')

 

😽 중복을 허용하지 않으므로, 파이썬에서 hash table을 사용한 집합인 set을 사용한다.

😽 set의 in operation은 O(1)로, list의 in operation O(N) 대비 효율이 좋아 위와 같은 여러 정보를 입력할 때 매우 유용하게 사용 가능.

---

★ 17219 비밀번호 찾기 ★

 

import sys
input=sys.stdin.readline

N,M=map(int,input().split())

d=dict()

for j in range(N):
    address,password=input().split()
    d[address]=password

for k in range(M):
    print(d[input().rstrip()])

 

😽 비밀번호와 주소 총 2가지 정보를 저장해야 하고, 비밀번호를 입력하면 주소를 바로 찾아주는 hash table을 만들면 끝!

---

★ 20291 파일 정리 ★

 

import sys
input=sys.stdin.readline

dic={}
for _ in range(int(input())):
    name=input().rstrip().split('.')[1]
    if len(dic) == 0:
        dic[name] = 1
    else:
        if name in dic.keys():
            dic[name]+=1
        else:
            dic[name]=1

sorted_dic = sorted(dic.items(), key=lambda item : item[0])

for tup in sorted_dic:
    print(tup[0], tup[1])

 

😽 hash map의 key는 파일 확장자 이름, 그리고 value는 각 확장자별 개수로 설정한다. keys()의 in 연산자는 O(1)로 쉽게 value를 더하거나 value를 1로 설정해 hash map을 업데이트 한다.

---

★ 7785 회사에 있는 사람 ★

 

import sys
input=sys.stdin.readline

l=set()

for _ in range(int(input())):
    name,kind=input().split()
    if kind=='enter':l.add(name)
    else:l.remove(name)

print(*sorted(l,reverse=True),sep='\n')

 

😽 set 집합으로 만들어 (동명이인이 없으므로 집합 만들기 가능) add()와 remove()라는 O(1) 시간 복잡도의 효율적인 method를 활용해 성능을 높였다. 최종 시간복잡도는 sorted()의 O(nlogn)으로 코드 완성!

---

★ 1269 대칭 차집합 ★

 

import sys
input=sys.stdin.readline
input()
print(len(set(map(int,input().split()))^set(map(int,input().split()))))

 

😽 대칭 차집합 ^를 바로 사용하면 끝!

---

★ 14425 문자열 집합 ★

 

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
S=set()
for _ in range(N):
    S.add(input())
ans=0
for _ in range(M):
    if input() in S: ans += 1
print(ans)

---

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

 

S=input()
ans=set()

for l in range(1,len(S)+1):
    for i in range(len(S)-l+1):
        ans.add(S[i:i+l])
print(len(ans))

 

😽 집합에 add()로 부분적인 연속 문자열을 넣어서, 자동적으로 서로 다른(중복을 허용하지 않는) 집합의 길이를 출력하면 끝! 서로 다르다는 성질을 집합이라는 자료구조와 연결해서 문제를 효율적인 코드로 해결할 수 있다.

---

★ 25325 학생 인기도 측정 ★

 

import sys
input=sys.stdin.readline
n,d=int(input()),dict()
for i in input().split():d[i]=0
for i in range(n):
    for j in input().split():d[j]+=1
for x in sorted(d.items(),key=lambda x:(-x[1],x[0])):print(*x)

 

😽 인기도와 이름이라는 두 개의 정보를 활용해 효율적인 자료구조 dictionary를 만들고 dictionary sorting으로 한 번에 정답 출력!

---

★ 9612 Maximum Word Frequency ★

 

import sys
input=sys.stdin.readline

tf_idf=dict()
for _ in range(int(input())):
    w=input().strip()
    if w in tf_idf: tf_idf[w] += 1
    else: tf_idf[w] = 1

print(*sorted(tf_idf.items(),key=lambda item:(item[1],item[0]),reverse=True)[0])

 

😽 단어와 빈도수 두 개의 정보를 저장하는 dictionary 구조를 사용하고, value가 제일 큰 것이 오고, value가 같다면 사전 순 뒤의 단어가 먼저 나오게 하기 위해서는 먼저 value sort하고, key sort한 뒤 reverse하면 된다! (key sort는 lexicographical order이므로 reverse하면 됨) dictionary sort code에서 (item[1], item[0])으로 설정하고 reverse=True

---

★ 11645 I've Been Everywhere, Man ★

 

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    city=set()
    for _ in range(int(input())):
        city.add(input().rstrip())
    print(len(city))

 

😽 중복을 허용하지 않는 자료구조 set()의 add()로 update 후 distinct city 개수 len(set) 출력

---

★ 26069 붙임성 좋은 총총이 ★

 

import sys
input=sys.stdin.readline
dancing=set()
dance_start=False
for _ in range(int(input())):
    x,y=input().rstrip().split()
    if 'ChongChong' in [x,y]:
        dance_start=True
        dancing.add(x)
        dancing.add(y)
        continue
    if dance_start:
        if x in dancing or y in dancing:
            dancing.update([x,y])
print(len(dancing))

 

😽 총총이를 발견한 뒤부터 set()에 있는 캐릭터가 있다면 update 해 중복 없이 추는 캐릭터의 개수 출력하기. set()에서 in 연산자 O(1) 

---

★ 10184 Coupon2 ★

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    products=dict()
    invalid=[]
    X,Y=map(int,input().split())
    for _ in range(X):
        product_id,product_price=input().rstrip().split()
        products[product_id] = float(product_price)
    for _ in range(Y):
        product_id,discount=input().rstrip().split()
        discount=float(discount)
        if product_id not in products.keys():
            invalid.append(product_id)
        else:
            products[product_id]*=(1-discount)
    print(f'{sum(products.values()):.2f}')
    if invalid:
        print('INVALID COUPONS')
        for x in invalid:
            print(x)

---