백준(BOJ) 14171 Cities and States(Python)

문제 내용.

 

해싱 문제.

도시의 앞 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)

영어가 안 돼서 한참 헤맸다.

주가 같으면 안 된다는 걸 계속 이해를 못 하고 있었다.