백준 [단계별로 풀어보기]: (14단계) "집합과 맵", python

백준 [단계별로 풀어보기]: (14단계) "집합과 맵", python

 

1. 문제번호 및 정답비율

14단계 집합과 맵 : 문제번호 및 정답 비율

2. 문제별 필요 지식 및 풀이 포인트

# 1. 10815 숫자 카드

시간초과: list의 in 연산자는 매우 느리므로, 시간초과가 생길 가능성이 높다.
# O(1)
i in _set
i in _dict
i in _dict.keys
# O(N)
i in list(_dict.keys())
i in [1,2,3]

list대신 set을 사용해볼까? => OK

좌표압축 18870에서 썼던 방식처럼 딕셔너리를 활용해볼까? => OK

# 2. 14425 문자열 집합

# 3. 7785 회사에 있는 사람

딕셔너리 기본 유형 문제

퇴근시, del 딕셔너리[key값] 으로 삭제하며 아무것도 반환 않음 / pop(key값)은 삭제 후 해당 value를 반환

# 4. 1620 나는야 포켓몬 마스터 이다솜

dic()을 하나만 만들고 value로부터 key값 1개만을 갖고오는 방법은 없을까?

isdigit() : 숫자형태 / .isalpha() : 알파벳형태

# 5. 10816 숫자 카드2

이분탐색bisect(logN)로 풀겠다는 생각은 어떻게 떠올릴까

# 6. 1764 듣보잡

in set()일때 hashtable을 이용하므로 O(1)이지만, in list()일 때 O(N)이다.
set()에서 같은 원소값을 묶을 때 그냥 & 하면 된다.

# 7. 1269 대칭 차집합

# 8. 11478 서로 다른 부분 문자열의 개수 / 어려움, 차후에 다시 풀어보기

리스트슬라이싱써야되나? 틀렸습니다 뜸
왠지 out of range가 뜨기도 하니 중간값을 잡고 양끝으로 넓혀가듯이 탐색하면 될거 같은데

'''집합(set)연산자 정리'''
a = {1,2,4}
b = {2,3,4,5,6}

while True:
    #집합연산자
    print(set.union(a,b), a|b) #합집합
    print(set.intersection(a,b), a&b) #교집합
    print(set.difference(a,b), a-b) #차집합
    print(set.symmetric_difference(a,b), a^b) #대칭차집합
    #집합연산자(2): 리턴값 TrueorFalse
    print(set.issubset(a,b), a.issubset(b), a<=b) #부분집합(두set이 같아도 True)
    print(a<b) #진부분집합: 부분집합이지만 같지 않을때에만 True
    print(set.issuperset(a,b), a.issuperset(b), a>=b) #상위집합
    print(a>b) #진상위집합
    print(set.isdisjoint(a,b), a.isdisjoint(b)) #겹치는요소가 있으면, False

    #집합연산 후 할당연산자(=)사용
    a|={5}; #a.update({5})
    print(a) #{1,2,4,5,6}
    a-={5}; #a.difference_update({5})
    print(a) #{1,2,4}
    a&={1,2}; #a.intersection_update({1,2})
    print(a) #{1,2}
    a^=b; #a.symmetric_difference_update(b)
    print(a) #{1,2,4,5,6}
    break

3. 문제별 풀이 코드

# 1. 10815 숫자 카드
'''시간초과: list의 in 연산자는 매우 느리므로, 시간초과가 생길 가능성이 높다.
# O(1)
i in _set
i in _dict
i in _dict.keys

# O(N)
i in list(_dict.keys())
i in [1,2,3]
'''
'''list대신 set을 사용해볼까? => OK'''
n = int(input())
n_l = set(map(int, input().split())) #list()대신 set()
m = int(input())
m_l = list(map(int, input().split()))

for i in m_l: #O(N)
    if i in n_l: #O(1)
        print(1, end=' ')
    else:
        print(0, end=' ')

'''좌표압축18870에서 썼던 방식처럼 딕셔너리를 활용해볼까? => OK'''
n = int(input()) #5
n_l = list(map(int, input().split())) #6 3 2 10 -10
m = int(input()) #8
m_l = list(map(int, input().split())) #10 9 -5 2 3 4 5 -10

dic = {} #dict()
for i in range(len(n_l)):
    dic[n_l[i]] = 0 #{6:0, 3:0, 2:0, 10:0, -10:0}
for j in range(m): #0~7
    if m_l[j] in dic: #ex) 10 in dic
        print(1, end=' ')
    else:
        print(0, end=' ')
        
'''다른 고수들의 숏코딩'''
#p,q,r,s=open(0)
#d={*q.split()}
#print(*[+(i in d)for i in s.split()])
f=open(0)
while True:
    line = f.readline()
    if not line:
        break
    print(line)
f.close()


# 2. 14425 문자열 집합
n, m = map(int, input().split()) #5 11
s = set([input() for _ in range(n)]) #s는 집합이라 했으므로
#print(s) #{'',''}꼴
count = 0
for i in range(m):
    s_ = input() #m의 문자열은 input 받자마자 집합s랑 비교해서 카운트
    if s_ in s:
        count += 1
print(count)


# 3. 7785 회사에 있는 사람
'''딕셔너리 기본 유형 문제'''
n = int(input())
dic = dict() #1)딕셔너리
for _ in range(n):
    name, state = input().split()
    
    if state == 'enter': #2)출입시, key:value = name:state로 받음
        dic[name] = state
    else: #퇴근시, del 딕셔너리[key값] 으로 삭제하며 아무것도 반환 않음 / pop(key값)은 삭제 후 해당 value를 반환
        del dic[name]

dic = sorted(dic.keys(), reverse=True) #사전 역순 정렬

for key in dic:
    print(key)


# 4. 1620 나는야 포켓몬 마스터 이다솜
'''dic()을 하나만 만들고 value로부터 key값 1개만을 갖고오는 방법은 없을까?'''
n, m = map(int, input().split()) #26 5
dic = dict()
index = dict()
for i in range(1, n+1): #{1:'abc', 2:'def', ...}꼴
    name = input()
    dic[i] = name
    index[name] = i
for j in range(m):
    answer = input()
    if answer.isdigit(): #isdigit():숫자형태 / .isalpha():알파벳형태
        print(dic[int(answer)])
    else:
        print(index[answer])


# 5. 10816 숫자 카드2
'''이분탐색bisect(logN)로 풀겠다는 생각은 어떻게 떠올릴까'''
n = int(input())
n_ = list(map(int, input().split())) #6 3 2 10 10 10 -10 -10 7 3
m = int(input())
m_ = list(map(int, input().split())) #10 9 -5 2 3 4 5 -10
'''시간초과
    for i in range(m):
    if m_[i] in n_:
        print(n_.count(m_[i]), end= ' ')
    else:
        print(0, end= ' ')'''
dic = dict()
for i in n_:
    if i in dic:
        dic[i] += 1 #{6:1, 3:2, 2:1, 10:3, -10:2, 7:3}
    else:
        dic[i] = 1


# 6. 1764 듣보잡
'''in set()일때 hashtable을 이용하므로 O(1)이지만, in list()일때 O(N)
set()에서 같은 원소값을 묶을 때 그냥 & 하면 된다.
'''
'''for i in list: 시간초과
n, m = map(int, input().split())
n_ = [input() for _ in range(n)]
m_ = [input() for _ in range(m)]
for i in n_:
    if i in m_:
        print(i)
'''
n, m = map(int, input().split())
n_ = set([input() for _ in range(n)])
m_ = set([input() for _ in range(m)])
answer = sorted(list(n_&m_)) #set()의 원소를 교집합&으로 묶고 오름차순배열화
print(len(answer))
for i in answer:
    print(i)
for j in m_:
    if j in dic:
        print(dic[j], end=' ')
    else:
        print(0, end=' ')


# 7. 1269 대칭 차집합
a, b = map(int, input().split()) #3 5
a_ = set(map(int, input().split())) #1 2 4
b_ = set(map(int, input().split())) #2 3 4 5 6
print(len(a_-b_)+len(b_-a_))
'''zenith님풀이'''
_ = input()
a = set(map(int, input().split()))
a ^= set(map(int, input().split()))
print(len(a))


# 8. 11478 서로 다른 부분 문자열의 개수
'''리스트슬라이싱써야되나? 틀렸습니다 뜸
왠지 out of range가 뜨기도 하니 중간값을 잡고 양끝으로 넓혀가듯이 탐색하면 될거 같은데'''
s = list(input())
result = []
for i in range(len(s)):
    result.append(s[i])
for i in range(1,len(s)):
    result.append(s[i-1]+s[i])
for i in range(2,len(s)):
    result.append(s[i-2]+s[i-1]+s[i])
for i in range(3, len(s)):
    result.append(s[i-3]+s[i-2]+s[i-1]+s[i])
for i in range(4, len(s)):
    result.append(s[i-4]+s[i-3]+s[i-2]+s[i-1]+s[i])
answer = set(result)
print(len(answer))