숫자 카드2(10816) / 듣보잡(1764)

해시테이블을 이용하는 기초적인 두 문제

• 하단 영상에서 추천해주신 문제를 풀어보았다.

• 코딩테스트 문제 추천! (2023년 1월 2주차)

숫자 카드2 (10816) [실버 IV]

• 10816번: 숫자 카드 2
• Github

# 0. 입력 받기
n = int(input())
total = [card for card in map(int, input().split())]
m = int(input())
sangeun = [card for card in map(int, input().split())]

# 1. 해시 태이블을 만들자. {card: count} -> [핵심]
count = {}
for card in total:
    count[card] = count.setdefault(card, 0) + 1
    """
    위 구문을 풀어쓰면
    
    if card not in count:
        count[card] = 1
    else:
        count[card] += 1
    """

# 2. num 개수를 뽑아보자.
answer = ""
for card in sangeun:
    print(count.setdefault(card, 0), end=" ")
    """
    위 구문을 풀어쓰면
    
    if card not in count:
        answer += str(0) + " "
    else:
        answer += str(count[card]) + " "

이걸 숙지하면 다음처럼 string으로 변환을 굳이 안해도 된다.
print(answer[:-1])
"""

• 핵심은 써놨듯이 카드의 개수를 기반으로 한 해시테이블 생성하는 것이다.
• 이를 통해 별다른 추가 연산 없이, 전체 배열을 도는 것 없이, 빠르게 개수에 접근 가능하다.
• Dictionary로 구성하는 것이 제일 적합할 것으로 보인다.

듣보잡 (1764) [실버 IV]

• 1764번: 듣보잡
• Github

# 0. 입력받기
n, m = map(int, input().split())

# 1. 입력 받으면서 해시 테이블 바로 생성
# 듣도 보도 못한 사람들을 전체적으로 확인해야하므로
# 두 명단 리스트를 통합해도 된다고 판단.
nohearsee = {}
for i in range(n + m):
    name = input()
    nohearsee[name] = nohearsee.setdefault(name, 0) + 1
    
# 2. 듣도보도 못한사람을 모두 뽑아보자.
# 각 명단에서 중복 인원은 없다고 했으므로
# 듣도 + 보도 못했다면 테이블에서 값은 2일 것.
answer = []
for name in nohearsee:
    if nohearsee[name] == 2:
        answer.append(name)

# 3. 알파벳 순 정렬 및 개수 출력
answer = sorted(answer)
print(len(answer))
for name in answer:
    print(name)

• 처음 풀 때는 간단하게 전체 리스트를 돌게 한다.
• 돌면서 해시테이블 상으로 2로 기록되는 것을 답안으로 채택했다.

# 시간 개선하기 -> 100ms 더 느려지던데..?

# 0. 입력받기
n, m = map(int, input().split())

# 1. 입력 받으면서 해시 테이블 바로 생성
# 듣도 못한 사람들만 우선 확인한다.
nohear = {}
for i in range(n):
    name = input()
    nohear[name] = nohear.setdefault(name, 0) + 1
    
# 2. 듣도보도 못한사람을 모두 뽑아보자.
# 듣지 못한 사람들 중에서 보도 못한 사람을 키로 받아
# 존재한다면 듣도 + 보도 못한 사람이 되는 것.
answer = []
for i in range(m):
    name = input()
    if name in nohear:
        answer.append(name)

# 3. 알파벳 순 정렬 및 개수 출력
answer = sorted(answer)
print(len(answer))
for name in answer:
    print(name)

• 영상 해설에서는 두번째 리스트를 키로 활용했다.
• 더 직관적이나 시간 차이 크게 없었다.

• 상위가 2번째 코드, 하위가 1번째 코드