김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 27888 가희와 지하철역 저장 시스템 1 파이썬(Python)

문제 링크

비트마스킹으로 분류가 되어있는데 안 써도 어찌저찌 풀 수는 있는 해시맵(딕셔너리) 문제.
원래 의도는 9가지 피쳐에 대해서 비트마스킹하여 정수로 바꾸고 인덱싱을 통해 문제를 해결하는 것 같은데, 그렇게 하지 않고 튜플을 키로 하는 딕셔너리를 써도 충분히 풀린다.
일단 핵심은, 피처 개수가 최대 9개라는 것인데, 따라서 경우의 수는 \(2^9\)가지이다.
그리고, 이걸 비트마스킹으로 풀지 않는 경우 itertools.combinations()를 사용해서 1개~9개를 선택하는 조합의 경우의 수를 모두 확인하면 된다.
eki_rev[key]는 역 key가 가진 피쳐들을 저장하고 있는 딕셔너리이고, eki[key]는 피쳐들의 튜플 key를 검색했을 때 나와야 하는 답(즉 해당 키워드를 모두 가진 역의 개수)을 저장하고 있는 딕셔너리이다.
명령어를 하나씩 실행하면서 이 두 개의 딕셔너리를 갱신하고 확인해나가면 된다.

#!python

from sys import stdin
from itertools import combinations
from collections import defaultdict
input = stdin.readline

# eki[key]는 key 피처 조합을 가진 역의 개수(key는 튜플)
# eky_rev[key]는 key라는 역의 피처 종류 리스트
eki = defaultdict(int)
eki_rev = defaultdict(list)

# 역 이름은 그냥 패스.. defaultdict를 쓸 거기 때문
n = int(input())
for _ in range(n):
    input()

# 명령어 처리
m = int(input())
for _ in range(m):
    # U인 경우 st[0]에 역 이름이 담기고
    # G인 경우 st는 빈 리스트가 된다
    op, *st, feats = input().split()
    feats = tuple(sorted(feats.split(',')))
    # U 연산인 경우
    if op == 'U':
        # 원래 역에 있던 피쳐 정보를 통해서 해당 피쳐에 해당하는 역의 개수를 감소시킨다
        for i in range(len(eki_rev[st[0]])):
            # 가능한 경우는 조합을 하면 되는데, 순서에 유의해야 하기에 앞서서 feats를 정렬해 주었다
            for e in combinations(eki_rev[st[0]], i + 1):
                eki[e] -= 1
        # 새로 들어온 피쳐 정보를 가지고 해당 피쳐에 해당하는 역의 개수를 증가시킨다
        for i in range(len(feats)):
            # 마찬가지로 조합을 통해서 가능한 경우를 알아내면 된다
            for e in combinations(feats, i + 1):
                eki[e] += 1
        # 역에 있는 피쳐 정보를 갱신
        eki_rev[st[0]] = feats
    # G 연산인 경우
    else:
        # 있으면 개수 출력
        if feats in eki:
            print(eki[feats])
        # 없으면 0 출력
        # defaultdict라 그냥 예외처리 안 해도 되긴 하는데, 10개 이상의 태그가 생겨서 성능에 영향을 미칠까봐 처리했다
        else:
            print(0)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑