[백준] 집합과 맵 연습문제 (1764번, 10815번, 14425번, 7785번)

1764번: 듣보잡

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력:
듣보잡의 수와 그 명단을 사전순으로 출력한다.

 

문제를 보자마자 "교집합->set을 이용하자" 를 떠올렸다. Intersection 메소드를 이용해 아래와 같이 작성하였다. 이때 출력을 사전순으로 해야 하기 때문에, sorted를 해주고 iteration을 하자.

M, N = map(int, input().split())
d = set()
b = set()
for _ in range(M):
    d.add(input())
for _ in range(N):
    b.add(input())
db = d.intersection(b)
print(len(db))
for element in sorted(db):
    print(element)

 

10815번: 숫자 카드

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력:
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

지난 번 풀었던 탐색 알고리즘 (1920번) 과 상당히 유사한 문제이다. "in" 연산자를 이용해서 iteration을 돌리면서, 해당 자료구조 안에 데이터가 있는지 판단하면 된다. 처음에는 숫자 카드 목록을 리스트로 받아서 해결했는데, 시간 초과가 났다. (기억하자!! 리스트에서 in 연산자를 쓰면 linear searching이 되므로 O(N)의 시간 복잡도를 가진다) 따라서, 해시 탐색으로 구현되어 O(1)의 시간 복잡도로 연산할 수 있는 set으로 숫자 카드 목록을 변경하여 아래와 같이 작성하였다.

N = int(input())
cards = set(map(int, input().split()))
M = int(input())
temp = list(map(int, input().split()))
for item in temp:
    print(int(item in cards), end = ' ')

 

14425번: 문자열 집합

 

총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 
다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.
입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력:
첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

 

앞선 문제와 마찬가지로, set으로 N개의 줄을 받아서 주어지는 M개의 문자열들에 대해 iteration을 돌리면서 개수를 세 주면 된다. 리스트로 풀면 시간 효율성 측면에서 비효율적이다.

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

 

7785번: 회사에 있는 사람

 

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.
각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력:
현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

 

회사에 있는 사람들을 저장하는 자료구조를 만들어, 추가 및 삭제를 해야 하는 문제이다. 자료의 처음 혹은 마지막에 있는 사람을 빼는 형태였다면 다른 자료구조를 선택했겠지만, 입력받은 이름을 빼야 하므로 searching이 들어가야 한다. 따라서, 이전 문제들과 마찬가지로 set을 쓰자.

n = int(input())
people = set()
for _ in range(n):
    person, status = input().split()
    if status[0] == 'e':
        people.add(person)
    else:
        people.remove(person)
for item in sorted(people, reverse=True):
    print(item)