ABC212 C - Min Difference를 풀어 보았습니다.



이중 for로 전체 탐색해도 되지만, 계산량이 4*10^10이 되어, TLE가 된다.
실 입을 찾기 위해, 우선 샘플을 확인해 본다.



개인적으로 주목한 것은 입력 예 3.
최소값을 찾는 것은 수열 A , 수열 B 중에서 값이 가까운 요소의 조합을 내면 좋지?

여기에서 더욱 도약이 들어갑니다.
그럼, 수열 A 와 수열 B 를 합체해 sort 하면 A[n]=>B[m] or B[m]=>A[n] 이 되는 줄이 반드시 있어,
그 중에서 차이가 최소가 되는 조합을 찾으면 좋지?

라고 말하는 것으로, 이것으로 갈 수 있었습니다.

MinDifference_1.py
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

A = list(set(A))#A の重複要素を排除
B = list(set(B))#B の重複要素を排除

#A,B を合体すると、ごちゃまぜで分からなくなるので、
#辞書で管理することにしました。
dicA = {}
dicB = {}

for i in range(len(A)):
    dicA[A[i]] = 1#冒頭で set() してるので重複要素なし、要素は必ず 1 つ
for i in range(len(B)):
    dicB[B[i]] = 1#冒頭で set() してるので重複要素なし、要素は必ず 1 つ

X = A + B # AとB を合体
X.sort()  # sort する

ans = float("inf") # 無限大より小さいものを for で探す

#辞書はリストに無い key の所在を尋ねると Error を返します。
#if X[i] in dicA としても良かったかもだが、dicA/dicB の要素数が計算量として上乗せされる。
#そのため 2*10^5 x 2*10^5 となる可能性があるので記述は避けた。
#代わりに try / except を使って計算量を抑えた.
for i in range(len(X)-1):#=> X を端から確認し、X[i],X[i+1] の差分をcheck。
    try:
        if dicA[X[i]] == 1 and dicB[X[i+1]] == 1:#辞書で X[i],X[i+1] がそれぞれ A,B であることを確認
            if abs(X[i]-X[i+1]) < ans:
                ans = abs(X[i]-X[i+1])
    except:#上記で Error で返したら、以下の処理に入る
        try:
            if dicB[X[i]]==1 and dicA[X[i+1]]==1:#辞書で X[i],X[i+1] がそれぞれ A,B であることを確認
                if abs(X[i] - X[i + 1]) < ans:
                    ans = abs(X[i] - X[i + 1])
        except:
            pass#上記でもダメなら pass。次の検証に向かう
print(ans)

분명, 더 알기 쉽고 좋은 해법이 있을 것.



우선, 다른 사람의 해법도 읽으면서 이미지를 쌓아 보려고 한다.
감동하면 추기할지도.

이해가 어리석은지도 모르지만,
위의 경우의 계산량은 O(N)라고 생각하지만 다르지 않을까?
지식인의 조언이 있으면 도움이 될 것입니다 m (_ _) m

그때부터



아직도 적지만 여러가지 풀어 견식이 퍼졌다고 믿고, 재챌린지.
이하에서도 다녔다.

MinDifference_2.py
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

dicA = {}
dicB = {}

for n in range(N):
    if A[n] not in dicA:
        dicA[A[n]] = 0
    dicA[A[n]] += 1

for m in range(M):
    if B[m] not in dicB:
        dicB[B[m]] = 0
    dicB[B[m]] += 1

X = A + B
X.sort()
score = float("inf")
for i in range(N+M-1):#max O(4*10**5)
    if X[i] in dicA and X[i+1] in dicB or X[i] in dicB and X[i+1] in dicA:
        score = min(score,abs(X[i]-X[i+1]))
print(score)

개선점



· A/B 중복 삭제 설명을 제거합니다.
만일 중복이 있었다고 해도 전술에 있듯이 O(4*10^5)이므로 계산량은 문제가 되지 않고, 대답이 바뀌지 않는다.
· try/except의 설명 삭제
사전의 in연산은 O(1)이므로 강간 사용하는 것으로 기술이 계산량을 신경쓰지 않고, 간단하게 쓸 수 있다.

좋은 웹페이지 즐겨찾기