0405

SoniaComp · SoniaComp · commit c3e597333e84 · 2021-04-06T09:47:07.000+09:00
diff --git a/interview/dp/abbreviation_1.py b/interview/dp/abbreviation_1.py
@@ -0,0 +1,42 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+
+# Complete the abbreviation function below.
+def abbreviation(a, b):
+    if len(b) > len(a):
+        return 'NO'
+    if len(b) == len(a):
+        a = a.upper()
+        return 'YES' if a == b else 'NO'
+    
+    ap = bp = 0
+    while ap < len(a):
+        if bp < len(b) and (a[ap] == b[bp] or a[ap].upper() == b[bp]):
+            ap += 1
+            bp += 1
+        elif a[ap].islower():
+            ap += 1
+        else:
+            break
+    return 'YES' if bp == len(b)-1 and ap == len(a) else 'NO'
+
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    q = int(input())
+
+    for q_itr in range(q):
+        a = input()
+
+        b = input()
+
+        result = abbreviation(a, b)
+
+        fptr.write(result + '\n')
+
+    fptr.close()
diff --git a/interview/dp/abbreviation_2.py b/interview/dp/abbreviation_2.py
@@ -0,0 +1,40 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+
+# Complete the abbreviation function below.
+def isEqual(a, b):
+    return a==b or a.upper()==b
+
+def abbreviation(a, b):
+    A_LEN = len(a)
+    B_LEN = len(b)
+    DP = [[False]*B_LEN for _ in range(A_LEN)]
+    DP[0][0] = isEqual(a[0], b[0]) or a[0].islower()
+    for i in range(1, A_LEN):
+        for j in range(B_LEN):
+            if j >= 0 and DP[i-1][j-1] and isEqual(a[i], b[j]):
+                DP[i][j] = True
+            if DP[i-1][j] and a[i].islower():
+                DP[i][j] = True
+    return "YES" if DP[A_LEN-1][B_LEN-1] else "NO"
+
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    q = int(input())
+
+    for q_itr in range(q):
+        a = input()
+
+        b = input()
+
+        result = abbreviation(a, b)
+
+        fptr.write(result + '\n')
+
+    fptr.close()
diff --git a/interview/dp/candy_1.py b/interview/dp/candy_1.py
@@ -0,0 +1,44 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+
+# Complete the candies function below.
+def candies(n, arr):
+    dp = [0]*n
+    dp[0] = 1
+    pivot = 0
+    for i in range(1, n):
+        if arr[i] > arr[i-1]:
+            dp[i] = dp[i-1] + 1
+            pivot = i
+        else:
+            dp[i] = 1
+            if pivot + 1 < i:
+                for idx in range(i-1, pivot, -1):
+                    dp[idx] = dp[idx+1] + 1
+                if dp[pivot] < dp[pivot+1]:
+                    dp[pivot] = dp[pivot+1] + 1
+                    
+    print(dp)
+    return sum(dp)
+
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    n = int(input())
+
+    arr = []
+
+    for _ in range(n):
+        arr_item = int(input())
+        arr.append(arr_item)
+
+    result = candies(n, arr)
+
+    fptr.write(str(result) + '\n')
+
+    fptr.close()
diff --git a/interview/dp/candy_2.py b/interview/dp/candy_2.py
@@ -0,0 +1,41 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+
+# Complete the candies function below.
+def candies(n, arr):
+    dp = [1]*n
+    for i in range(1, n):
+        if arr[i] > arr[i-1]:
+            dp[i] = dp[i-1] + 1
+    
+    for j in range(n-1, 0, -1):
+      if arr[j] < arr[j-1] and dp[j] >= dp[j-1]:
+        dp[j-1] = dp[j] + 1
+    
+    return sum(dp)
+
+                    
+    print(dp)
+    return sum(dp)
+
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    n = int(input())
+
+    arr = []
+
+    for _ in range(n):
+        arr_item = int(input())
+        arr.append(arr_item)
+
+    result = candies(n, arr)
+
+    fptr.write(str(result) + '\n')
+
+    fptr.close()
diff --git a/interview/greedy/luck_1.py b/interview/greedy/luck_1.py
@@ -0,0 +1,38 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+
+# Complete the luckBalance function below.
+def luckBalance(k, contests):
+    contests.sort(key=lambda x: (-x[1], x[0]))
+    loose_count = len(list(filter(lambda x: x[1]==1, contests))) - k
+    sum_count = 0
+    for contest in contests[loose_count:]:
+        sum_count += contest[0]
+    for contest in contests[:loose_count]:
+        sum_count -= contest[0]
+    return sum_count
+
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    nk = input().split()
+
+    n = int(nk[0])
+
+    k = int(nk[1])
+
+    contests = []
+
+    for _ in range(n):
+        contests.append(list(map(int, input().rstrip().split())))
+
+    result = luckBalance(k, contests)
+
+    fptr.write(str(result) + '\n')
+
+    fptr.close()
diff --git a/interview/search/minimum_time.py b/interview/search/minimum_time.py
@@ -0,0 +1,22 @@
+def findItems(machines,temp):
+    ans = 0
+    for i in range(len(machines)):
+        ans += temp // machines[i]
+    return ans
+
+def BinarySearch(machines,goal,high):
+    low = 1
+    while low < high:
+        mid = (low + high) >> 1
+        item = findItems(machines,mid)
+        if item < goal:
+            low = mid + 1
+        else:
+            high = mid
+    return high
+# Complete the minTime function below.
+def minTime(machines, goal):
+    maxval = -float('inf') 
+    for i in range(len(machines)): 
+        maxval = max(maxval, machines[i]) 
+    return BinarySearch(machines,goal,maxval * goal)
diff --git a/interview/search/pairs_1.py b/interview/search/pairs_1.py
@@ -0,0 +1,41 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+
+# Complete the pairs function below.
+def pairs(k, arr):
+    count = 0
+    arr.sort()
+    left, right = 0, 1
+    while right < len(arr) and left < len(arr):
+        diff = arr[right] - arr[left]
+        if diff > k:
+            left += 1
+        elif diff < k:
+            right += 1
+        else:
+            count += 1
+            left += 1
+            right += 1
+    return count
+
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    nk = input().split()
+
+    n = int(nk[0])
+
+    k = int(nk[1])
+
+    arr = list(map(int, input().rstrip().split()))
+
+    result = pairs(k, arr)
+
+    fptr.write(str(result) + '\n')
+
+    fptr.close()
diff --git a/interview/search/pairs_2.py b/interview/search/pairs_2.py
@@ -0,0 +1,36 @@
+#!/bin/python3
+# greedy &#54620; &#54644;&#48277;
+import math
+import os
+import random
+import re
+import sys
+
+# Complete the pairs function below.
+def pairs(k, arr):
+    count = 0
+    d = {}
+    for i in arr:
+        d[i] = i
+    for j in arr:
+        g = j + k
+        if g in d:
+            count += 1
+    return count
+
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    nk = input().split()
+
+    n = int(nk[0])
+
+    k = int(nk[1])
+
+    arr = list(map(int, input().rstrip().split()))
+
+    result = pairs(k, arr)
+
+    fptr.write(str(result) + '\n')
+
+    fptr.close()
diff --git a/interview/search/triple_1.py b/interview/search/triple_1.py
diff --git a/interview/search/triple_2.py b/interview/search/triple_2.py
@@ -0,0 +1,54 @@
+#!/bin/python3
+
+import math
+import os
+import random
+import re
+import sys
+from bisect import bisect
+# Complete the triplets function below.
+
+def triplets(a, b, c):
+    a = sorted(list(set(a)))
+    b = sorted(list(set(b)))
+    c = sorted(list(set(c)))
+    
+    ai = 0
+    bi = 0
+    ci = 0
+
+    ans = 0
+
+
+    while bi < len(b):
+      while ai < len(a) and a[ai]<=b[bi]:
+        ai += 1
+      while ci < len(c) and c[ci] <=b[bi]:
+        ci += 1
+      ans += ai*ci
+      bi += 1
+    
+    return ans
+    
+if __name__ == '__main__':
+    fptr = open(os.environ['OUTPUT_PATH'], 'w')
+
+    lenaLenbLenc = input().split()
+
+    lena = int(lenaLenbLenc[0])
+
+    lenb = int(lenaLenbLenc[1])
+
+    lenc = int(lenaLenbLenc[2])
+
+    arra = list(map(int, input().rstrip().split()))
+
+    arrb = list(map(int, input().rstrip().split()))
+
+    arrc = list(map(int, input().rstrip().split()))
+
+    ans = triplets(arra, arrb, arrc)
+
+    fptr.write(str(ans) + '\n')
+
+    fptr.close()
diff --git a/interview/string/special_1.py b/interview/string/special_1.py
diff --git a/interview/string/special_2.py b/interview/string/special_2.py
