해싱 문제.
도시의 앞 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)
영어가 안 돼서 한참 헤맸다.
주가 같으면 안 된다는 걸 계속 이해를 못 하고 있었다.
'BOJ' 카테고리의 다른 글
백준(BOJ) 2195 문자열 복사(Python) (0) | 2023.01.17 |
---|---|
백준(BOJ) 24524 아름다운 문자열(Python) (0) | 2023.01.14 |
백준(BOJ) 10942 팰린드롬?(Python) (0) | 2023.01.14 |
백준(BOJ) 11497 통나무 건너뛰기(Python) (0) | 2023.01.13 |
백준(BOJ) 25393 교집합 만들기(Python) (0) | 2023.01.13 |