ABC202 C - Made Up을 풀어 보았습니다.



평소와 같이 i, j를 각각 for로 중첩하여 전체 탐색하면
TLE로 떨어집니다. 우선 샘플을 바라본다



for 문에서 B [C [i] -1]에 대해 i로 돌려 보자.
그때 B[C[i]-1] 과 같은 값이 배열 A 안에 몇 개 있는지 계산하면 좋을 것 같다.
라고 하는 것은 사전에 사전에서 A 에 대해 정리해 두면 해결한다고 생각했다.

MadeUp.py
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

#A の中に何の要素が何個ずつ入っているのか管理
dic = {}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]] = 0
    dic[A[i]] += 1

score = 0
for i in range(N):
    try:
        score += dic[B[C[i]-1]]#該当したら、その個数を積み上げる
    except:
        pass# B[C[i]-1] が辞書内に存在しないと言われたら pass する
print(score)

atcoder problem 회색 0으로 절반 정도의 레벨이라면 C 문제라도 어떻게든. .
조금씩 레벨을 올려 가고 싶은 곳이군요.



잘못해도 다음과 같이하지 않는 것이 좋다고 생각합니다.

MadUp_TLE.py
N = int(input())
A = list(map(str,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A = "".join(A)
score = 0
#以下のように O(N^2) となるので TLE となります。
for i in range(N): #=> N
    score += A.count(str(B[(C[i])-1])) # => N : 
                                       # count は都度 A の中を要素数(N) だけ探索してカウントするため
                                       # 計算量は N と認識されます。
print(score)

좋은 웹페이지 즐겨찾기