15. (딕셔너리, 집합) 숫자카드 2, 서울에서 김서방 찾기, 베스트셀러, 놀라운 문자열

 

 

숫자카드 2

 

 

N = int(input())
cards = list(map(int, input().split()))
M = int(input())
queries = list(map(int, input().split()))
new_queries = []

for i in range(M):
    new_queries.append(cards.count(queries[i]))

print(new_queries)

하지만 위와같이 하면 시간 초과가 걸림 : count()는 리스트 전체를 처음부터 끝가지 세면서 검사하기 때문에 O(N) : 근데 그걸 M번 반복하니까 전체 복잡도는 O(NxM) : 문제에서 M, N은 50만이 최대인데 파이썬은 보통 1초에 10^7(1억)정도 연산 가능 : N × M = 500,000 × 500,000 = 250,000,000,000 (2.5 × 10^11) : 시간초과

 

어떻게 해결해야할까? : 카드들을 먼저 한번만 훑어서 각 숫자의 개수를 해시테이블(딕셔너리)에 저장 : O(N) : 하고 그걸 조회만 하면? : O(M) : 즉, O(N+M) : 딕셔너리는 내부적으로 해시 함수를 써서 키(key)를 저장함 : 키, 값 매핑을 한번에 바로 접근 가능한 즉시 찾기에 최적화된 자료구조 : 위와같이 빠른 탐색을 할 때 유용

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

new_cards = {}
for i in cards:
    # 이미 있으면 +1
    if i in new_cards:
        new_cards[i] += 1
    # 없으면 딕셔너리에 새로 추가하고 1로 지정
    else:
        new_cards[i] = 1

new_queries = []
for j in queries:
    if j in new_cards:
        new_queries.append(str(new_cards[j]))
    else:
        new_queries.append("0")

print(" ".join(new_queries))

파이썬에서 join()은 리스트(혹은 튜플)에 있는 문자열들을 하나로 이어붙일 때 씀 : 기본 형식은 아래와 같음

"구분자".join(리스트)

• "구분자" : 각 원소 사이에 끼워 넣을 문자열 (예: 공백 " ", 콤마 ",")
• 리스트 : 문자열 원소들로 이루어진 리스트

그리고 join은 문자열만 받을 수 있음 : 즉, 리스트 원소들을 모두 문자열로 반환하고 join을 쓰든가 해야함

 

번외 코드

배열을 사용해서 풀 순 없을까? : 해당 문제에서의 수 범위는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같음 : 배열을 하나 생성하여 -10,000,000 ~ 10,000,000 범위의 숫자를 모두 커버하도록 크게 생성하자 : 인덱스로 쓰는 것 : 이러면 카드 개수를 세는 과정은 O(N) 이지만, 쿼리 탐색 과정은 "인덱스로 바로 접근"이 되기 때문에 O(1)이라 문제 없음 : 즉, 공간을 써서 시간을 줄이는 것

OFFSET = 10000000
data = [0] * 20000010

for i in cards:
    data[i + OFFSET] += 1

new_queries = []
for j in queries:
    new_queries.append(str(data[j + OFFSET]))

 

음수를 처리하기 위해 OFFSET을 더해 양수 인덱스로 변환한 것

 

 

---

 

 

서울에서 김서방찾기

 

 

str 적용 후 +

def solution(seoul):
    dict_ = {}
    for idx, name in enumerate(seoul):
        dict_[name] = idx
    answer = "김서방은 " + str(dict_["Kim"]) + "에 있다"
    return answer

seoul = ["Jane", "Kim"]
print(str(solution(seoul)))

번외로 아래와 같이도 할 수 있음 : 새로안건 return에도 f""가 적용이 가능하다는것

     answer = seoul.index("Kim")
     return f"김서방은 {answer}에 있다"

 

 

---

 

 

베스트셀러

 

 

딕셔너리의 모든 값 추출하기(values)
values() 메서드 사용 : 딕셔너리의 모든 값을 추출하려면 values() 메서드를 사용하면 됨

>>> my_dict = {'name': '김철수', 'age': 30, 'city': '서울'}
>>> print(my_dict.values())

dict_values(['김철수', 30, '서울'])

 

딕셔너리의 모든 키 추출하기(keys)

파이썬 딕셔너리에서 키(key)들만 모아 보여주는 메서드 : values의 반환값과 똑같이 반복문에 쓰거나, list()함수를 써서 리스트로 변환해서 쓸 수 있음

d = {"a": 1, "b": 2, "c": 3}
print(d.keys())
# dict_keys(['a', 'b', 'c'])

 

추가로 알아두면 좋을 메서드(get, items)

get() 메서드 사용 : get() 메서드는 키가 존재하면 값을 반환하고, 키가 없을 경우 기본값(지정하지 않으면 None)을 반환

>>> my_dict = {'name': '김철수', 'age': 30, 'city': '서울'}
>>> print(my_dict.get('name'))
'김철수'

>>> print(my_dict.get('job', 'x')) # 키가 없으면 뒤에 지정해둔거 출력
'x'

items() 메서드 : 파이썬 딕셔너리에서 (키, 값) 쌍들의 객체 반환

>>> d = {"a": 3, "b": 5, "c": 2}
>>> print(d.items())
dict_items([('a', 3), ('b', 5), ('c', 2)])

 

 

최종코드

N = int(input())
titles = []
for i in range(N):
    titles.append(input())

dict_titles = {}
for i in titles:
    if i in dict_titles:
        dict_titles[i] += 1
    else:
        dict_titles[i] = 1

max_titles = max(dict_titles.values())

prt_titles = []
for i in dict_titles:
    if dict_titles[i] == max_titles:
        prt_titles.append(i)

print(sorted(prt_titles)[0])

sorted()[0]을 통해 사전순으로 정리 후 첫번째 값을 가져오는 방법도 있지만 : min() 함수를 써도 문자열끼리 자동으로 사전순 비교가 됨

print(min(["b", "a", "c"]))  # a

 

---

 

 

놀라운 문자열

 

 

string_ = input()
string_len = len(string_)
string_dict = {}

for i in range(string_len-1):
    string_dict[i] = []
    for j in range(string_len-1-i):
        string_dict[i].append(string_[j]+string_[j+i+1])

flag = True
for i in range(string_len-1):
    # 값을 리스트로 만들어 놓음 : 리스트 내의 중복값을 없애기 위해 set() 적용해서 중복 없애기
    if len(set(string_dict[i])) != string_len-1-i:
        flag = False
        break

if flag:
    print(1)
else:
    print(0)

문제 외적으로 고민했던 것 : for문으로 i를 늘려가면서, i(새 인덱스) → 거기 대응되는 값(리스트)을 매핑하려고 새 딕셔너리를 만듦 : 이게 유일한 방법인가? : 리스트/배열 대신 딕셔너리로 쓴 게 맞는 선택인가? : 딕셔너리가 지금까지 코딩하면서 유일하다고 생각했지만 리스트도 이중 for문 나가서 한번에 새 리스트 append하면 되는 방법이 있었음

string_list = []
for i in range(n-1):
    temp = []
    for j in range(n-1-i):
        temp.append(s[j] + s[j+i+1])
    string_list.append(temp)

 

근데 사실 위처럼 딕셔너리를 따로 만들 필요가 없음 : 검사할 때 바로 set에 넣어 중복 검사하면됨

string_ = input()
string_len = len(string_)
flag = True

for i in range(string_len - 1):
    seen = set()
    for j in range(string_len - 1 - i):
        pair = string_[j] + string_[j + i + 1]
        if pair in seen:       # 중복 발견
            flag = False
            break
        seen.add(pair)
    if not flag:
        break

print(1 if flag else 0)

 

집합은 튜플과 달리 수정이 가능함 : 대신 튜플의 장점인 중복 제거도 해줌 : set 주요 메서드는 아래와 같음

s = set()

# 1. 추가
s.add("A")                # 원소 1개 추가
s.update(["B", "C"])      # 여러 개 추가
print(s)                  # {'A', 'B', 'C'}

# 2. 삭제
s.remove("A")             # 'A' 삭제 (없으면 에러)
s.discard("Z")            # 'Z' 삭제 (없어도 에러 없음)
x = s.pop()               # 임의의 원소 제거 후 반환

s.clear()                 # 전체 삭제

 

 

---

 

 

결론

딕셔너리, 해시테이블은 공간을 써서 시간을 줄이게 되는 것임