Baekjoon 1764번 듣보잡

문제

https://www.acmicpc.net/problem/1764

걸린 시간

00 : 34 : 52

풀이

Python3

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    # 듣도 못한 사람의 수, 보도 못한 사람의 수
    N, M = map(int, input().split())

    no_hear = [[] for _ in range(0, 26+1)]

    no_hear_no_see = []

    dic = {chr(i):(i-0x61) for i in range(0x61, 0x7b)}

    for i in range(0, N):
        tmp = input().strip()
        no_hear[dic.get(tmp[0], -1)].append(tmp)

    for i in range(0, 26+1):
        if len(no_hear[i]) != 0:
            no_hear[i].sort()

    for i in range(0, M):
        tmp = input().strip()
        sl = dic.get(tmp[0], -1) # start letter
        left = 0
        right = len(no_hear[sl])-1
        while left <= right:
            mid = (left + right) // 2
            if tmp > no_hear[sl][mid]:
                left = mid + 1
            elif tmp < no_hear[sl][mid]:
                right = mid - 1
            else:
                no_hear_no_see.append(tmp)
                break

    # 듣도 보도 못한 사람의 수와 사전순으로 명단 출력
    no_hear_no_see.sort()
    print(len(no_hear_no_see))
    for i in no_hear_no_see:
        print(i)

듣도 못한 사람의 명단을 사전식으로 리스트에 저장하고 보도 못한 사람을 입력받은 후 리스트를 이분 탐색으로 검색해 중복되는 값들만 결과로 저장해 출력하였다.

다른 풀이

Python3

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N, M = map(int, input().split())

    no_hear = [input().strip() for _ in range(0, N)]
    no_see = [input().strip() for _ in range(0, M)]

    no_hear_no_see = list(set(no_hear) & set(no_see))

    no_hear_no_see.sort()

    print(len(no_hear_no_see))
    for i in no_hear_no_see:
        print(i)

키 값으로만 구성된 set 클래스 간의 교집합 연산을 이용한 풀이이다. 효율은 큰 차이가 없지만 코드가 정말 간단 명료하다.

또 다른 풀이

Python3

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N, M = map(int, input().split())

    no_hear = {input().strip():0 for _ in range(0, N)}

    for i in range(0, M):
        tmp = input().strip()
        if no_hear.get(tmp, -1) != -1:
            no_hear[tmp] += 1

    no_hear_no_see = []

    for key, value in no_hear.items():
        if value != 0:
            no_hear_no_see.append(i)

    no_hear_no_see.sort()

    print(len(no_hear_no_see))
    for i in no_hear_no_see:
        print(i)

키와 값으로 이루어진 딕셔너리 자료형을 사용하는 방법으로 키는 사람의 이름, 값은 중복 출현한 횟수로 사용한다. 세 코드 중에서 제일 효율이 좋다.