BOJ
백준(BOJ) 14171 Cities and States(Python)
juLeena
2023. 1. 14. 03:44
해싱 문제.
도시의 앞 2글자와 주 코드가 서로 교차 매칭되는 2개의 도시를 Special Pair라 한다.
이때 주의할 점은 두 도시가 서로 다른 주에 속해 있어야 한다는 것이다.
두 도시가 서로 Special Pair이면서 같은 주에 속해 있는 경우 두 도시의 앞 2글자는 서로 같다.
즉, 해당 도시의 앞 2글자와 주 코드가 모두 같은 경우이다.
따라서 도시와 주 코드를 해싱한 뒤 체크할 때 도시의 앞 2글자와 주 코드가 같은 경우는 빼고 체크하면 된다.
코드는 다음과 같다.
# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n=int(input())
D={}
L=[]
ans=0
for i in range(n):
a,b=input().rstrip().split()
x=a[:2]+b
if x not in D:
D[x]=1
else:
D[x]+=1
L.append((a[:2],b))
for i in range(n):
if L[i][0]==L[i][1]:
continue
if L[i][1]+L[i][0] in D:
ans+=D[L[i][1]+L[i][0]]
print(ans//2)
영어가 안 돼서 한참 헤맸다.
주가 같으면 안 된다는 걸 계속 이해를 못 하고 있었다.