Baekjoon - 집합과 맵

10815. 숫자 카드

 

Solution

n개의 정수들은 순서가 필요 없음 : Set

m개의 정수들은 순서 필요 : list 

=> 안에 존재하는지를 판단한다. (for문)

import sys
input = sys.stdin.readline

N = int(input())
N_set = set(map(int, input().split()))

M = int(input())
M_list = list(map(int, input().split()))

for i in M_list:
    if i in N_set:
        print("1", end=" ")
    else:
        print("0", end=" ")

 

14425. "문자열 집합"

 

String (N개) => 집합 S,,

S에 포함되어 있는 문자열이다.

M : 검사해야 하는 문자열의 개수

 

Solution

집합 S에 들어가 있는 문자열들은 순서가 필요 없음. -> Set 사용 (O(1))

set : 순서가 없고, 집합 안에서는 unique value, mutable.

검사해야 하는 문자열들은 순서가 필요함. -> List 사용

여기서 주의해야 할 점은 map도 객체이기 때문에 map을 직접 넣으면 Complie error가 발생할 수 있다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

S = set()
for i in range(N):
    S.add(input().strip()) # 공백을 제거 후 집합에 추가

count = 0 

for _ in range(M):
    if input().strip() in S:
        count += 1
        
print(count)

 

7785. "회사에 있는 사람"

 

Log가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 문제이다.

n : 출입 기록의 수

name은 enter (출근), leave (퇴근) 으로 나뉘는데, 단 동명이인이 없고 대소문자가 다르면 다른 이름이다.

 

Solution

1. Set 함수를 사용한다. (대소문자 구분 가능)

2. add, discard (keyerror x) function 사용

3. 정렬 (역순)

 

sys
Python 내장 module로, 시스템과 관련된 여러 기능을 제공한다.

sys.stdin.readline
표준 입력으로부터 한 줄씩 입력을 읽어들이는 함수이다.
장점은 빠른 입력을 처리할 수 있어서 input() function 보다 빠르다.
그리고, 대용량의 데이터를 처리할 수 있다.

 

import sys
input = sys.stdin.readline

n = int(input()) # 출입 기록의 수

S = set() # log를 저장할 집합

for i in range(n):
    name, log = input().split()
    if log == "enter":
        S.add(name)
    elif log == "leave":
        S.discard(name)


for i in sorted(S, reverse=True):
    print(i)

 

1620. "포켓몬 마스터"

도감에 수록되어 있는 포켓몬의 수 : N

내가 맞춰야 하는 문제의 개수 : M

-> 이걸 dictionary로 만들어서 진행한다.

 

1 <= (N, M) <= 100,000

Alphabet : 포켓몬 번호

숫자 : 포켓몬 번호에 해당하는 문자를 출력

 

Solution

1. dictionary 1, 2로 나누어 진행하는데 하나는 key-value를 포켓몬 번호 - 이름으로, 다른 dictionary는 포켓몬 이름 - 번호로 만들어서 진행한다.

근데, 문제는 모두 숫자, 모두 알파벳을 찾아야 하는게 문제인데, 이것을 찾아야 하는게 포켓몬 번호인지, 이름인지에 따라 각 dictionary에서 찾아서 출력한다.

 

주의! : 개행 문자를 제거하는 것이 필요하다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())  # N: 도감에 수록된 포켓몬의 개수, M: 문제의 개수

by_id = {}  # 포켓몬 번호 -> 이름 dictionary
by_name = {}  # 포켓몬 이름 -> 번호 dictionary

# 포켓몬 도감에 포켓몬을 수록
for i in range(1, N + 1):
    pokemon = input().strip()  # 개행 문자 제거 후 입력
    by_id[i] = pokemon  # 번호에 따른 포켓몬 이름 저장
    by_name[pokemon] = i  # 포켓몬 이름에 따른 번호 저장

# 문제 처리
for i in range(M):
    x = input().strip()  # 개행 문자 제거 후 입력
    if x.isdigit():  # 입력이 숫자인 경우
        print(by_id[int(x)])  # 숫자로 변환한 후 포켓몬 이름 출력
    else:  # 입력이 이름인 경우
        print(by_name[x])  # 포켓몬 번호 출력

 

10816. "숫자 카드2"

 

Solution

상근이가 가지고 있는 카드의 목록 : Set

문제 입력을 하나씩 진행한다.

 

근데, 숫자 카드 1과 다른 점은 숫자 카드가 중복이 될 수 있고 카운트해야 한다는 점 때문에 이 방법으로는 불가능하다.

1. 상근이와 문제에 들어갈 카드의 목록을 List로 선언

2. Counter 를 사용해서 List 내 각 숫자의 등장 횟수를 자동 계산한다.

3. 각 결과를 문자열로 변환해서 List로 저장한 후, Join을 이용해서 공백으로 구분된 형태를 출력한다.

 

import sys
from collections import Counter

input = sys.stdin.readline

N = int(input()) # 상근이가 가지고 있는 숫자 카드의 개수

# 상근이가 가지고 있는 숫자 카드에 적힌 숫자 counting
cards = list(map(int, input().split())) 
card_count = Counter(cards) # 숫자 카드의 개수를 세는 Counter


M = int(input()) # 정수 M의 개수

# M개의 정수 입력
queries = list(map(int, input().split()))

# 각 정수에 대해 상근이가 몇 개 가지고 있는지 출력
result = []
for query in queries:
    result.append(str(card_count[query]))

# 공백으로 구분하여 결과 출력
print(" ".join(result))

 

1764. "듣보잡"

 

Solution

듣도 못한 사람 : Set

보도 못한 사람 : Set

-> S1 & S2 or S1.intersection(S2) 로 진행해서 듣보잡의 수와 그 명단을 출력 (사전순)

 

import sys
input = sys.stdin.readline

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

# 듣도 못한 사람 명단
not_heard = set()
for i in range(N):
    not_heard.add(input().strip()) # 개행문자 제거

# 보도 못한 사람 명단
not_seen = set()
for i in range(M):
    not_seen.add(input().strip()) # 개행문자 제거
    
# 듣도 보도 못한 사람 
not_heard_and_seen = sorted(not_heard & not_seen) # 사전순으로 정렬

# 듣보잡의 수 출력
print(len(not_heard_and_seen))

# 듣보잡 명단 출력
for name in not_heard_and_seen:
    print(name)

 

1269. "대칭 차집합"

 

Solution

A - B -> (A - B or A.differece(B))

B - A는 위와 구조는 동일하다.

따라서, 합집합인 | 기호를 사용하여 구하면 끝.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # n : A의 원소의 개수, m : B의 원소의 개수

n_set = set(map(int, input().split())) # A 집합
m_set = set(map(int, input().split())) # B 집합

answer = (n_set - m_set) | (m_set - n_set)
print(len(answer))

 

11478. "서로 다른 부분 문자열의 개수"

 

Solution

1. indexing 을 이용하여 문자열을 잘라서 부분 문자열을 만든다. [i : j+1] 

=> indexing 은 -1이므로 i ~ j까지 범위를 반복하기 위해 j+1로 작성하였다.

2. dictionary 에 넣어서 각각 문자열의 길이를 파악한다.

3. 공백을 포함하지 않도록 주의,,

 

import sys
input = sys.stdin.readline

S = input().strip() # 문자열 입력

count = set()

for i in range(len(S)):
    for j in range(i + 1, len(S) + 1):
        count.add(S[i:j]) 

print(len(count))