https://www.acmicpc.net/problem/2002
initial
So observing the patterns, I solved it like a human. I reversed the given list to iterate more easily and when we have a decreasing subsequence, we set tmp as that lower value and continue. But once we meet value 0 (0-indexed), we increment ans(count) and break out of loop. We return n-ans for the final answer.
But we dont need defaultdict(list), just a normal declaration of dictionary will do. This is cuz we are appending just 1 value to our key, not a list. Using this list as value made the impl more confusing.
solution
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
ori = [input().strip() for _ in range(n)]
change = [input().strip() for _ in range(n)]
dic = defaultdict(list)
ans = 0
for i in range(n):
dic[ori[i]].append(i)
i += 1
change.reverse()
tmp = int(10e18)
for i in range(n):
if dic[change[i]][0] < tmp:
if dic[change[i]][0]==0:
ans+=1
break
else:
ans+=1
tmp = dic[change[i]][0]
print(n-ans)without defaultdict(list) and using normal dict
this is opp from my impl where it checks from the front (not the back like my impl).
N = int(input())
answer = 0
enter, out = dict(), []
for i in range(N):
car = input()
enter[car] = i
for _ in range(N):
car = input()
out.append(car)
for i in range(N-1):
for j in range(i+1, N):
if enter[out[i]] > enter[out[j]]:
answer += 1
break
print(answer)complexity
The time complexity of this code is O(n) because it goes through the n elements in the ori and change lists once.
The space complexity is also O(n) because it uses a dictionary dic that stores lists of indices for each unique value in the ori list.
Your code seems to be counting how many elements from the end of the change list can be matched to elements from the beginning of the ori list. The code then calculates n - ans to get the count of unmatched elements in the ori list.
Overall, the code is efficient with a linear time complexity.
